Meeting Rooms II
Given a list of meeting time intervals [start, end), find the minimum number of conference rooms needed so that no two overlapping meetings share a room.
- 1 ≤ intervals.length ≤ 10^4
- 0 ≤ start < end ≤ 10^6
- Rooms needed = maximum number of simultaneous intervals
- Sort by start; track the earliest-ending active meeting
- Min-heap of end times
Sort by start (or end) time and sweep: two intervals overlap iff the next start is before the current end, and after sorting each interval only needs comparing with the one being built. Counting concurrent intervals is a sweep over sorted endpoints, or a min-heap of end times.
Sort meetings by start time. Keep a min-heap of end times for meetings currently occupying rooms. For each meeting, if the earliest end time in the heap is ≤ its start, that room is free — pop it. Push the new meeting's end time. The largest heap size reached is the answer, because it equals the peak number of overlapping meetings.
- A sweep line over sorted start and end events with a counter also gives O(n log n) and avoids the heap; a difference array works when times are small integers.