2402

2402. Meeting Rooms III (Hard)

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:

1. Each meeting will take place in the unused room with the lowest number.
2. 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.
3. 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.

Companies: Google, Uber

Related Topics:
Array, Sorting, Heap (Priority Queue)

Similar Questions:

• Meeting Rooms (Easy)
• Meeting Rooms II (Easy)
• Maximum Number of Events That Can Be Attended (Easy)
• Find Servers That Handled Most Number of Requests (Easy)
• Maximum Number of Events That Can Be Attended II (Easy)

Solution 1. Heap

Sort the meetings in ascending order of start time.

We keep a min-heap roomsInUse whose elements are pairs of {end time, room number} of those rooms in-use. The room with the earliest end time is at the top.

We scan meetings one by one. To find a room for the current meeting, we free all the rooms in roomsInUse that ends before the start time of the current meeting.

There are two additional cases to consider:

1. If there is no meeting room available, and the end time of the next available room e is greater than the start time of the current meeting, then we must postpone the current meeting to start at e.
2. After postponing a meeting to start at time e, the subsequent meetings that starts before time e needs to be postponed as well to at least time e. So, we need to log the start time used by the previous meeting prevStartTime, and the next meeting's start time should be at least prevStartTime.

After freeing rooms, we pick the smallest room index from set availableRooms.

// OJ: https://leetcode.com/problems/meeting-rooms-iii
// Author: github.com/lzl124631x
// Time: O(MlogN)
// Space: O(N)
class Solution {
public:
    int mostBooked(int n, vector<vector<int>>& A) {
        sort(begin(A), end(A), [](auto &a, auto &b) { return a[0] < b[0]; });
        auto cmp = [](auto &a, auto &b) { return a[0] > b[0]; };
        priority_queue<vector<long>, vector<vector<long>>, decltype(cmp)> roomsInUse(cmp); // end time, room number. The room with the smallest end time is at the top
        vector<int> usage(n);
        long prevStartTime = -1;
        set<int> availableRooms;
        for (int i = 0; i < n; ++i) availableRooms.insert(i);
        for (auto &m : A) {
            long start = m[0], end = m[1], duration = end - start;
            if (start < prevStartTime) { // if the current start time is earlier than the previous start time, this meeting must be at least postponed to the same start time as the previous one
                start = prevStartTime;
                end = start + duration;
            }
            if (availableRooms.empty() && roomsInUse.top()[0] > start) { // if no rooms are available, and the end time of the next available meeting room is greater than start time of the current meeting, we need to postpone this current meeting
                start = roomsInUse.top()[0];
                end = start + duration;
            }
            while (roomsInUse.size() && roomsInUse.top()[0] <= start) {
                availableRooms.insert(roomsInUse.top()[1]);
                roomsInUse.pop();
            }
            prevStartTime = start;
            int room = *availableRooms.begin();
            ++usage[room];
            availableRooms.erase(room);
            roomsInUse.push({end, room});
        }
        return max_element(begin(usage), end(usage)) - begin(usage);
    }
};

Solution 2. Heap

// OJ: https://leetcode.com/problems/meeting-rooms-iii
// Author: github.com/lzl124631x
// Time: O(MlogN)
// Space: O(N)
class Solution {
public:
    int mostBooked(int n, vector<vector<int>>& A) {
        sort(begin(A), end(A), [](auto &a, auto &b) { return a[0] < b[0]; });
        priority_queue<vector<long>, vector<vector<long>>, greater<>> roomsInUse; // end time, room number. The room with the smallest end time, or the smallest room number when there are multiple rooms with the same smallest end time, is at the top.
        vector<int> usage(n);
        set<int> availableRooms;
        for (int i = 0; i < n; ++i) availableRooms.insert(i);
        for (auto &m : A) {
            long start = m[0], end = m[1], room;
            while (roomsInUse.size() && roomsInUse.top()[0] <= start) {
                availableRooms.insert(roomsInUse.top()[1]);
                roomsInUse.pop();
            }
            if (availableRooms.size()) {
                room = *availableRooms.begin();
                availableRooms.erase(room);
                roomsInUse.push({end, room});
            } else {
                long time = roomsInUse.top()[0];
                room = roomsInUse.top()[1];
                roomsInUse.pop();
                roomsInUse.push({ time + end - start, room });
            }
            ++usage[room];
        }
        return max_element(begin(usage), end(usage)) - begin(usage);
    }
};