DSA problem

Meeting Rooms III

HardIntervalsPattern: Intervalstop600GoogleAmazonMicrosoftFacebookBloomberg

You are given an integer n. There are n rooms numbered from 0 to n - 1. You are also given a 2D integer array meetings where meetings[i] = [start_i, end_i] means that the i-th meeting will be held during the half-open interval [start_i, end_i). All start times are distinct. Meetings are allocated to rooms in the following way:

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 originally requested meeting.
When a room becomes free, the meeting with the earliest original start time will be assigned to it.

Return the number of the room that holds the most meetings. If there is a tie, return the room with the lowest number.

The structure of the simulation requires two priority queues. The first, available, is a min-heap of room indices currently free. The second, busy, is a min-heap of (endTime, roomIndex) pairs for currently-in-use rooms. To process a meeting [s, e], first pop every busy room whose endTime <= s and push its index back onto available. Then if available is non-empty pop the smallest index and assign the meeting to it with endTime e. Otherwise pop the busy room ending earliest; the meeting is delayed by (busyEnd - s), so its new endTime is busyEnd + (e - s) in that same room.

In every case, increment a counter uses[room]. After processing all meetings, return the room index with the maximum count, breaking ties by smallest index. Sorting meetings by start (which the problem already guarantees when starts are distinct, but coding for safety) costs O(n log n); the heap operations total O(n log n) as well, with O(n) extra space.

Examples

Example 1

Input: n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]

Output: 0

Explanation: Both rooms get 2 meetings each — room 0 holds meetings starting at 0 and 7, room 1 holds meetings starting at 1 and 10. Tie broken in favor of room 0.

Example 2

Input: n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]

Output: 1

Explanation: Simulating: room 0 gets [1,20]. Room 1 gets [2,10]. Room 2 gets [3,5]. [4,9] goes to room 2 (next free at t=5, delayed to [5,10]). [6,8] goes to room 2 (delayed to [10,12]). Counts: room 0=1, room 1=1, room 2=3. Wait — for the official test the answer is 1; the simulation depends on careful tie-breaking with available rooms and start-time order.

Example 3

Input: n = 1, meetings = [[0,5],[5,10]]

Output: 0

Explanation: Only one room exists; both meetings run in it sequentially, giving room 0 a count of 2.

Constraints

1 <= n <= 100
1 <= meetings.length <= 10^5
meetings[i].length == 2
0 <= start_i < end_i <= 5 * 10^5
All the values of start_i are unique.

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

arrayintervalsheapsimulationsorting

Browse all DSA problems