GreedyGreedy
Interval Partitioning (minimum rooms)
The family of interval problems: unweighted selection (greedy by finish), interval partitioning into minimum rooms (greedy by start with a min-heap), and weighted selection (DP with binary search).
A
A
A
A
A
B
B
C
C
C
C
D
D
D
E
E
E
F
F
F
Intervals (input order)
| id | start | end | state |
|---|---|---|---|
| A | 0 | 5 | — |
| B | 1 | 3 | — |
| C | 2 | 6 | — |
| D | 4 | 7 | — |
| E | 6 | 9 | — |
| F | 8 | 11 | — |
1/166 intervals all have to happen; the question is how many rooms we must open so that no two overlapping intervals share one. Every column where several rows are filled is a moment that needs that many rooms at once, so the answer can never be smaller than the deepest column.
Interval being assignedRoom 1Room 2Room 3Room 4 (further rooms reuse colours — the cell shows the room number)
PseudocodeLearn Interval Scheduling →
1sort intervals by start time2heap = empty min-heap of room finish times3for (s, f) in sorted order:4 if heap is non-empty and heap.min <= s:5 room = pop the heap # that room is free again6 else:7 room = open a new room # every open room is still busy8 push (f, room) back onto the heap9return rooms opened # == maximum overlap depthVariables
intervals6
horizon11
Complexity
worst O(n log n)
space O(n)
Speed