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:**
-
\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.
Open the full interactive solver, hints, and worked solution →