Meeting Rooms II

Problem

A conference center needs to schedule all submitted meetings without cancelling any. Each meeting has a fixed [start, end] time window and must have its own room for its full duration. Given all meeting intervals, find the minimum number of conference rooms required to accommodate every meeting.

Example 1:

Input: [[2,25],[7,12],[16,22]]
Output: 2
Explanation: [2,25] overlaps both [7,12] and [16,22], so 2 rooms are needed.

Example 2:

Input: [[9,13],[4,7]]
Output: 1
Explanation: The meetings do not overlap, so one room is enough.

Example 3:

Input: [[2,6],[3,7],[4,8],[5,9]]
Output: 4
Explanation: All four meetings overlap at time 5, so each needs its own room.

Constraints:

• 0 <= intervals.length <= 2000
• 0 <= start < end <= 10^5

Solution Breakdown

Approach: sweep meetings by start time, track live rooms in a min-heap of end times.

Sort the meetings by start so you process them in the order they begin. The heap rooms holds the end times of every meeting currently using a room, with the soonest-to-free room sitting at rooms[0]. For each meeting, ask the cheapest question: has any room freed up by the time this meeting starts? That is exactly rooms and rooms[0] <= start. If yes, the earliest-ending room is now empty, so reuse it with heapreplace(rooms, end) - pop the old end time and push this meeting's end in one step. If no room is free (or none exist yet), open a new one with heappush(rooms, end). The heap only ever grows when a genuinely concurrent meeting arrives, so its final size is the peak number of simultaneously running meetings - which is the minimum rooms required.

Checking only rooms[0] is enough because it is the earliest end time in the heap: if even the soonest-freeing room is still busy, every other room is too. Trace [[2,25],[7,12],[16,22]] sorted: [2,25] opens room 1; [7,12] starts at 7 with 7 < 25, open room 2; [16,22] starts at 16, and rooms[0]=12 <= 16, so reuse - heap stays size 2. Answer 2.

Edge cases: an empty list returns 0 before any heap work; meetings that merely touch (one ends at t, the next starts at t) reuse the room because the condition is <=, not <.

Complexity: O(n log n) time - the sort plus n heap operations each O(log n); O(n) space for the heap when all meetings overlap.