##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2402.html

# 2402. Meeting Rooms III

• Difficulty: Hard.
• Related Topics: Array, Sorting, Heap (Priority Queue).
• Similar Questions: Meeting Rooms, Meeting Rooms II, Maximum Number of Events That Can Be Attended, Find Servers That Handled Most Number of Requests, Maximum Number of Events That Can Be Attended II.

## Problem

You are given an integer n. There are n rooms numbered from 0 to n - 1.

You are given a 2D integer array meetings where meetings[i] = [starti, endi] means that a meeting will be held during the half-closed time interval [starti, endi). All the values of starti are unique.

Meetings are allocated to rooms in the following manner:

• Each meeting will take place in the unused room with the lowest number.

• If there are no available rooms, the meeting will be delayed until a room becomes free. The delayed meeting should have the same duration as the original meeting.

• When a room becomes unused, meetings that have an earlier original start time should be given the room.

Return** the number of the room that held the most meetings. If there are multiple rooms, return the room with the lowest number.**

A half-closed interval [a, b) is the interval between a and b including a and not including b.

Example 1:

Input: n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
Output: 0
Explanation:
- At time 0, both rooms are not being used. The first meeting starts in room 0.
- At time 1, only room 1 is not being used. The second meeting starts in room 1.
- At time 2, both rooms are being used. The third meeting is delayed.
- At time 3, both rooms are being used. The fourth meeting is delayed.
- At time 5, the meeting in room 1 finishes. The third meeting starts in room 1 for the time period [5,10).
- At time 10, the meetings in both rooms finish. The fourth meeting starts in room 0 for the time period [10,11).
Both rooms 0 and 1 held 2 meetings, so we return 0.


Example 2:

Input: n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
Output: 1
Explanation:
- At time 1, all three rooms are not being used. The first meeting starts in room 0.
- At time 2, rooms 1 and 2 are not being used. The second meeting starts in room 1.
- At time 3, only room 2 is not being used. The third meeting starts in room 2.
- At time 4, all three rooms are being used. The fourth meeting is delayed.
- At time 5, the meeting in room 2 finishes. The fourth meeting starts in room 2 for the time period [5,10).
- At time 6, all three rooms are being used. The fifth meeting is delayed.
- At time 10, the meetings in rooms 1 and 2 finish. The fifth meeting starts in room 1 for the time period [10,12).
Room 0 held 1 meeting while rooms 1 and 2 each held 2 meetings, so we return 1.


Constraints:

• 1 <= n <= 100

• 1 <= meetings.length <= 105

• meetings[i].length == 2

• 0 <= starti < endi <= 5 * 105

• All the values of starti are unique.

## Solution (Java, C++, Python)

• class Solution {
public int mostBooked(int n, int[][] meetings) {
int ans[] = new int[n];                                                     //for numbers of usages
PriorityQueue<int[]> ends = new PriorityQueue<>
(n, (int[] o1, int[] o2) -> o2!=o1 ? o1-o2 : o1-o2);    //end , room
TreeSet<Integer> rooms = new TreeSet<>();                                   //for empty rooms
for(int i = 0; i != n; i++) rooms.add(i);                                   //check all rooms as empty
Arrays.sort(meetings, (int[] o1, int[] o2) -> o1 - o2);               //sorting for minimal starts

for(int[] m: meetings){
while(!ends.isEmpty() && ends.peek() <= m) rooms.add(ends.poll());       //empty all rooms for current time

if(!rooms.isEmpty()){                                          //if we have empty rooms
int room = rooms.pollFirst();                                //fetch room with minimal number
ans[room]++;                                                 //check it as used
ends.add(new int[]{m, room});                             //and put it into queue
}else{                                                     //if we not have any empty room
int[] e = ends.poll();                                   //fetch from queue first room that will be empty
ans[e]++;                                             //and again use it (check it as used)
ends.add(new int[]{e + m - m, e});           //and reuse it with correct time
}
}

int maxi = 0, id = -1;                          //fetch minimal index from array with numbers of usages
for(int i = 0; i != n; i++)
if(ans[i] > maxi) {maxi = ans[i]; id = i;}

return id;
}
}

############

class Solution {
public int mostBooked(int n, int[][] meetings) {
Arrays.sort(meetings, (a, b) -> a - b);
PriorityQueue<int[]> busy
= new PriorityQueue<>((a, b) -> a == b ? a - b : a - b);
PriorityQueue<Integer> idle = new PriorityQueue<>();
for (int i = 0; i < n; ++i) {
idle.offer(i);
}
int[] cnt = new int[n];
for (var v : meetings) {
int s = v, e = v;
while (!busy.isEmpty() && busy.peek() <= s) {
idle.offer(busy.poll());
}
int i = 0;
if (!idle.isEmpty()) {
i = idle.poll();
busy.offer(new int[] {e, i});
} else {
var x = busy.poll();
i = x;
busy.offer(new int[] {x + e - s, i});
}
++cnt[i];
}
int ans = 0;
for (int i = 0; i < n; ++i) {
if (cnt[ans] < cnt[i]) {
ans = i;
}
}
return ans;
}
}

• class Solution:
def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
meetings.sort()
busy = []
idle = list(range(n))
heapify(idle)
cnt =  * n
for s, e in meetings:
while busy and busy <= s:
heappush(idle, heappop(busy))
if idle:
i = heappop(idle)
cnt[i] += 1
heappush(busy, (e, i))
else:
a, i = heappop(busy)
cnt[i] += 1
heappush(busy, (a + e - s, i))
ans = 0
for i, v in enumerate(cnt):
if cnt[ans] < v:
ans = i
return ans

############

# 2402. Meeting Rooms III
# https://leetcode.com/problems/meeting-rooms-iii/

class Solution:
def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
meetings.sort(key = lambda x: x)
usedCount =  * n
h = []
freshRooms = []

for roomId in range(n):
heappush(freshRooms, (0, roomId))

for start, end in meetings:
temp = []

while h and h < start:
endTime, roomId = heappop(h)
temp.append((start, roomId))

for endTime, roomId in temp:
heappush(h, (endTime, roomId))

duration = end - start

if not h or (freshRooms and h and h > start):
endTime, roomId = heappop(freshRooms)
else:
endTime, roomId = heappop(h)

usedCount[roomId] += 1
d = endTime + duration if endTime != 0 else end
heappush(h, (d, roomId))

maxUsed = max(usedCount)

for roomId, count in enumerate(usedCount):
if count == maxUsed:
return roomId

return -1


• using ll = long long;
using pii = pair<ll, int>;

class Solution {
public:
int mostBooked(int n, vector<vector<int>>& meetings) {
priority_queue<int, vector<int>, greater<int>> idle;
priority_queue<pii, vector<pii>, greater<pii>> busy;
for (int i = 0; i < n; ++i) idle.push(i);
vector<int> cnt(n);
sort(meetings.begin(), meetings.end());
for (auto& v : meetings) {
int s = v, e = v;
while (!busy.empty() && busy.top().first <= s) {
idle.push(busy.top().second);
busy.pop();
}
int i = 0;
if (!idle.empty()) {
i = idle.top();
idle.pop();
busy.push({e, i});
} else {
auto x = busy.top();
busy.pop();
i = x.second;
busy.push({x.first + e - s, i});
}
++cnt[i];
}
int ans = 0;
for (int i = 0; i < n; ++i) {
if (cnt[ans] < cnt[i]) {
ans = i;
}
}
return ans;
}
};

• func mostBooked(n int, meetings [][]int) int {
sort.Slice(meetings, func(i, j int) bool { return meetings[i] < meetings[j] })
idle := hp{make([]int, n)}
for i := 0; i < n; i++ {
idle.IntSlice[i] = i
}
busy := hp2{}
cnt := make([]int, n)
for _, v := range meetings {
s, e := v, v
for len(busy) > 0 && busy.end <= s {
heap.Push(&idle, heap.Pop(&busy).(pair).i)
}
var i int
if idle.Len() > 0 {
i = heap.Pop(&idle).(int)
heap.Push(&busy, pair{e, i})
} else {
x := heap.Pop(&busy).(pair)
i = x.i
heap.Push(&busy, pair{x.end + e - s, i})
}
cnt[i]++
}
ans := 0
for i, v := range cnt {
if cnt[ans] < v {
ans = i
}
}
return ans
}

type hp struct{ sort.IntSlice }

func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() interface{} {
a := h.IntSlice
v := a[len(a)-1]
h.IntSlice = a[:len(a)-1]
return v
}

type pair struct{ end, i int }
type hp2 []pair

func (h hp2) Len() int { return len(h) }
func (h hp2) Less(i, j int) bool {
a, b := h[i], h[j]
return a.end < b.end || a.end == b.end && a.i < b.i
}
func (h hp2) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *hp2) Push(v interface{}) { *h = append(*h, v.(pair)) }
func (h *hp2) Pop() interface{}   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }


Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).