Meeting Rooms III
Hard · Heap & Counting · Array · Hash Table · Sorting · Heap (Priority Queue) · Simulation
Problem
There are n rooms numbered 0 to n - 1. You are given meetings, where meetings[i] = [start_i, end_i] is a meeting over the half-open interval [start_i, end_i). All start times are distinct.
Meetings are assigned as follows:
- Each meeting takes the lowest-numbered free room.
- If no room is free, the meeting waits until a room frees up, then runs for its original duration from that moment. If several rooms free up at the same time, it takes the lowest-numbered one.
- When a room frees up, waiting meetings are served in order of their original start time.
Return the room that hosted the most meetings. If several rooms tie, return the lowest-numbered one.
Examples
Input: n = 2, meetings = [[0,10],[1,2],[3,4],[5,6]] Output: 1
Room 0 is busy until 10, so the three short meetings all go to room 1.
Input: n = 2, meetings = [[0,5],[1,3],[2,4],[6,7]] Output: 0
[2,4) waits for room 1 and runs [3,5); [6,7) takes room 0, so both rooms host two meetings and room 0 wins the tie.
Input: n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]] Output: 1
Rooms 0, 1 and 2 take the first three. [4,9) waits for room 2 (free at 5) and runs [5,10); [6,8) waits for room 1 (free at 10, tied with room 2 but lower) and runs [10,12). Rooms 1 and 2 host two each, and room 1 is the lower.
Constraints
- 1 <= n <= 100
- 1 <= len(meetings) <= 10^5
- meetings[i] = [start_i, end_i]
- 0 <= start_i < end_i <= 5 · 10^5
- all start_i are distinct
Approaches
- Sort by start, scan every room per meeting — time O(m log m + m · n), space O(n)
Follow-up
What if meetings could be cancelled, or rooms had different capacities? Cancellations call for lazy deletion in the busy heap (skip entries that are no longer valid when they reach the top). With capacities, the free set becomes “smallest room that fits”: a sorted structure keyed by capacity instead of a plain heap of room numbers.
Related problems
Start free on Cariara · Coding problems · System design studio
