Meeting Rooms II

You are given meeting time intervals where intervals[i] = [start_i, end_i]. Each meeting uses one room for the entire half-open time range [start_i, end_i). Return the minimum number of rooms needed so every meeting can happen without conflict.

Input / output

• Input: intervals: int[][]
• Output: minimum number of rooms needed

Examples

1. intervals = [[0,30],[5,10],[15,20]] returns 2 because the meetings [0,30) and [5,10) overlap.
2. intervals = [[7,10],[2,4]] returns 1 because the meetings do not overlap.
3. intervals = [[1,5],[2,3],[3,6]] returns 2 because one room can host [2,3) then [3,6), while [1,5) still needs another room.

Constraints

• 0 <= intervals.length <= 10^5
• intervals[i].length == 2
• 0 <= start_i < end_i <= 10^6

Target complexity

• Aim for O(n log n) time and O(n) extra space or better.

Hints

1. Separate all start times from all end times, then sort both lists.
2. When the next meeting starts before the earliest ending active meeting finishes, you need one more room; otherwise you can reuse a room.

Follow-up How would you modify the algorithm to return an actual room assignment for each meeting, not just the count?