# Meeting Rooms III - LeetCode Daily Challenge

## Problem Statement

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] = [start`

means that a meeting will be held during the _{i}, end_{i}]**half-closed** time interval `[start`

. All the values of _{i}, end_{i})`start`

are _{i}**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.
```

Try here before watching the video.

### Video Explanation

### Java Code

```
class Solution {
public int mostBooked(int n, int[][] meetings) {
PriorityQueue<Integer> rooms = new PriorityQueue<>((a, b) -> (a-b));
for(int i = 0; i < n; i++) {
rooms.add(i);
}
PriorityQueue<Meeting> occupied = new PriorityQueue<>((a, b) -> ((a.end == b.end) ?
(a.room - b.room) : (a.end - b.end)));
int[] roomUtilization = new int[n];
Arrays.sort(meetings, (a,b) -> a[0]-b[0]);
for(int i = 0; i < meetings.length; i++) {
int start = meetings[i][0];
int end = meetings[i][1];
while(!occupied.isEmpty() && occupied.peek().end <= start) {
rooms.add(occupied.poll().room);
}
if(!rooms.isEmpty()) {
int room = rooms.poll();
occupied.add(new Meeting(start, end, room));
roomUtilization[room] += 1;
} else {
Meeting meeting = occupied.poll();
int diff = meeting.end - start;
occupied.add(new Meeting(start + diff, end + diff, meeting.room));
roomUtilization[meeting.room] += 1;
}
}
int room = -1, maxValue = 0;
for(int i = 0; i < n; i++) {
if(maxValue < roomUtilization[i]) {
maxValue = roomUtilization[i];
room = i;
}
}
return room;
}
class Meeting {
int start, end, room;
Meeting(int start, int end, int room) {
this.start = start;
this.end = end;
this.room = room;
}
}
}
```

### C++ Code

```
class Solution {
public:
struct Meeting {
long start, end;
int room;
Meeting(long start, long end, int room) : start(start), end(end), room(room) {}
};
int mostBooked(int n, vector<vector<int>>& meetings) {
auto cmpRooms = [](int a, int b) { return a > b; };
priority_queue<int, vector<int>, decltype(cmpRooms)> rooms(cmpRooms);
for(int i = 0; i < n; i++) {
rooms.push(i);
}
auto cmpMeetings = [](const Meeting& a, const Meeting& b) {
return (a.end == b.end) ? (a.room > b.room) : (a.end > b.end);
};
priority_queue<Meeting, vector<Meeting>, decltype(cmpMeetings)> occupied(cmpMeetings);
vector<int> roomUtilization(n, 0);
sort(meetings.begin(), meetings.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
});
for(const auto& meeting : meetings) {
int start = meeting[0];
int end = meeting[1];
while(!occupied.empty() && occupied.top().end <= start) {
rooms.push(occupied.top().room);
occupied.pop();
}
if(!rooms.empty()) {
int room = rooms.top();
rooms.pop();
occupied.push(Meeting(start, end, room));
roomUtilization[room] += 1;
} else {
Meeting meeting = occupied.top();
occupied.pop();
long diff = meeting.end - start;
occupied.push(Meeting(start + diff, end + diff, meeting.room));
roomUtilization[meeting.room] += 1;
}
}
int room = -1, maxValue = 0;
for(int i = 0; i < n; i++) {
if(maxValue < roomUtilization[i]) {
maxValue = roomUtilization[i];
room = i;
}
}
return room;
}
};
```

### Python Code

```
class Solution(object):
def mostBooked(self, n, meetings):
rooms, occupied = range(n), []
heapq.heapify(rooms)
meeting_count = [0] * n
for start, end in sorted(meetings):
while occupied and occupied[0][0] <= start:
_, room = heapq.heappop(occupied)
heapq.heappush(rooms, room)
if rooms:
room = heapq.heappop(rooms)
heapq.heappush(occupied, [end, room])
else:
room_availability_time, room = heapq.heappop(occupied)
heapq.heappush(
occupied,
[room_availability_time + end - start, room]
)
meeting_count[room] += 1
return meeting_count.index(max(meeting_count))
```

### Javascript Code

```
// remove this comment and paste the code here.
```

### Go Code

```
// remove this comment and paste the code here.
```

### Complexity Analysis

**Time Complexity: Space Complexity: **