Minimum Number of Rooms for Interval Partitioning
You are given $n$ intervals, each represented as $[s_i, e_i)$ (start inclusive, end exclusive). These represent meetings or events that each need a dedicated room. Two intervals can share a room only if they do not overlap.
Find the minimum number of rooms required so that every interval is assigned to a room with no overlaps. Additionally, output an explicit assignment of each interval to a room, and prove that your assignment is optimal.
Constraints:
- $1 \leq n \leq 10^5$
- $0 \leq s_i < e_i \leq 10^9$
- Intervals are half-open: $[s_i, e_i)$ means an interval ending at time $t$ does not conflict with one starting at time $t$
Example 1:
- Input:
intervals = [[0, 30), [5, 10), [15, 20)] - Output:
2 - Explanation:
[5, 10)and[15, 20)can share one room since they do not overlap.[0, 30)needs its own room. Total: 2 rooms.
Example 2:
- Input:
intervals = [[1, 5), [2, 6), [3, 7), [4, 8)] - Output:
4 - Explanation: At time 4, all four intervals are active simultaneously, so 4 rooms are required.
Example 3:
- Input:
intervals = [[1, 3), [3, 5), [5, 7)] - Output:
1 - Explanation: No two intervals overlap (they are end-to-start adjacent), so one room suffices.
Hints
- Think about what determines the lower bound on the number of rooms. What happens at the moment when the most meetings overlap?
- Sort intervals by start time and use a min-heap to track the earliest ending room. When a new meeting starts, check if the earliest-ending room is free.
- To prove optimality, argue that each time you open a new room, all existing rooms are occupied -- so the maximum heap size equals the maximum overlap depth, which is a lower bound.
Worked Solution
How to Think About It: This is the classic interval partitioning problem, also known as "meeting rooms II." The brute force approach -- try all possible assignments of intervals to rooms -- is exponential and clearly impractical. The key observation is that the minimum number of rooms equals the maximum number of intervals that overlap at any single point in time. If $k$ meetings are all happening simultaneously, you obviously need at least $k$ rooms. The beautiful part is that a simple greedy algorithm always achieves this lower bound exactly.
Algorithm: Sort all intervals by start time. Maintain a min-heap (priority queue) that tracks the end times of the rooms currently in use. For each new interval, check if its start time is at least as large as the smallest end time in the heap. If so, the earliest-finishing room is free -- reuse it by replacing its end time. If not, you need a new room -- push the new end time onto the heap. The heap size at the end is the answer, and by tracking which room each interval is assigned to, you get the explicit assignment.
To prove optimality: at any moment, the heap size equals the number of intervals currently active. The maximum heap size over the algorithm's run equals the maximum overlap depth. Since any valid assignment needs at least that many rooms, the greedy is optimal.
Code:
```python import heapq
def min_rooms(intervals): if not intervals: return 0, []
# Sort by start time, break ties by end time indexed = sorted(enumerate(intervals), key=lambda x: (x[1][0], x[1][1]))
# Min-heap of (end_time, room_id) heap = [] assignment = [0] * len(intervals) next_room = 0
for orig_idx, (start, end) in indexed: if heap and heap[0][0] <= start: # Reuse the room that frees up earliest _, room_id = heapq.heappop(heap) heapq.heappush(heap, (end, room_id)) assignment[orig_idx] = room_id else: # Allocate a new room heapq.heappush(heap, (end, next_room)) assignment[orig_idx] = next_room next_room += 1
return len(heap), assignment ```
Alternative sweep-line approach (just counting rooms, no assignment):
```python def min_rooms_sweep(intervals): events = [] for start, end in intervals: events.append((start, 1)) # meeting starts events.append((end, -1)) # meeting ends
events.sort() # ties: ends before starts (since -1 < 1) max_rooms = 0 current = 0 for _, delta in events: current += delta max_rooms = max(max_rooms, current) return max_rooms ```
Complexity:
- Time: $O(n \log n)$ -- dominated by the sort. Each heap operation is $O(\log n)$ and there are $n$ of them.
- Space: $O(n)$ -- the heap holds at most $n$ entries, and we store the assignment array.
Optimality Proof: Let $d$ be the maximum depth of overlap (the most intervals active at any single time point). Clearly, any valid assignment requires $\geq d$ rooms. The greedy algorithm opens a new room only when the current interval overlaps with all existing rooms -- which means $d$ intervals are simultaneously active. Therefore the greedy uses exactly $d$ rooms, matching the lower bound.
Answer: The minimum number of rooms equals the maximum overlap depth. A greedy algorithm sorting by start time and using a min-heap of end times solves this in $O(n \log n)$ time and $O(n)$ space, producing both the count and an explicit optimal assignment.
Intuition
The core insight is that the minimum number of rooms is determined by the maximum "congestion" -- the largest number of intervals that are all active at the same moment. This is a lower bound because if $k$ meetings overlap, you clearly need $k$ rooms. The greedy algorithm (process meetings in order of start time, reuse the earliest-available room) is optimal because it never opens a new room unless forced to -- and being forced means every existing room is busy, which means we have hit a new congestion peak.
This problem shows up constantly in scheduling and resource allocation. In quant work, the same sweep-line and greedy-assignment pattern appears when you need to count the maximum number of simultaneously open positions, allocate execution channels, or determine peak resource usage across parallel tasks. The sweep-line approach (create +1/-1 events and scan) is the fastest way to find peak overlap, while the heap approach gives you the actual assignment. Both are $O(n \log n)$ and both are tools you should have ready to go.