Meeting Rooms II

Problem

You are given a list of meetings, each a half-open time range [start, end). Every meeting must take place in a room, a room can host only one meeting at a time, and a room freed at time t can be reused by a meeting starting at t. Return the minimum number of rooms needed so that every meeting can be held as scheduled.

• Up to around ten thousand meetings.
• Start and end times are non-negative and fit comfortably in a normal int, with start < end.

Examples

• [[3,20],[8,12],[22,25]] → 2. The long meeting occupies one room for the whole span; the other two can share a second room because they do not overlap each other.
• [[9,12],[1,3]] → 1. No overlap at all.
• [[2,6],[6,9],[3,7]] → 2. At time 3 to 6 two meetings run at once; [6,9] can reuse the room freed by [2,6].

Hints

1. At any instant, how many rooms are busy? What is the relationship between that number over time and the answer?
2. Process meetings in start order. When a new meeting begins, which room would you most like to reuse, and how do you find it fast?
3. Min-heap of end times of meetings in progress; or a sweep over sorted start and end events counting concurrent meetings.