Meeting Rooms II

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

Example:

• Input: [[0,30],[5,10],[15,20]]
• Output: 2
• Explanation: Meeting 1 (0-30) requires a room. Meeting 2 (5-10) overlaps, so it needs a new room. Meeting 3 (15-20) also overlaps with Meeting 1, but it starts after Meeting 2 ends, so it can reuse Meeting 2's room.

Note: LeetCode 253, linked above, is a LeetCode Premium problem — opening it needs a Premium subscription. Everything needed to solve it is on this page.

The number of rooms needed is the most meetings running at the same moment. Two sorted arrays find it without tracking which meeting is in which room.

1. Sort the start times into starts and, separately, the end times into ends.
2. Walk the starts with i, keeping endPtr on the earliest end time not yet used.
3. Compare starts[i] with ends[endPtr]:
   • If starts[i] < ends[endPtr], no meeting has finished yet, so every room is busy: open a new room (rooms++).
   • Otherwise some meeting has already ended: its room is free, so reuse it and move endPtr to the next end time. The room count does not change.
4. Return rooms.

Only the count of finished meetings matters, not which one finished, which is why the start and end times can be sorted apart.

Alternative: sort the meetings by start and keep a min-heap of the end times of meetings in progress — pop the top when it is <= start, push the new end, and the heap's largest size is the answer. It is also O(N log N).

Watch how we allocate spaces (rooms) based on availability.