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.

Input: [[0,30],[5,10],[15,20]]    -> 2
Input: [[7,10],[2,4]]             -> 1
Input: [[1,5],[2,6],[3,7],[4,8]]  -> 4

Solution

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 [[0,30],[5,10],[15,20]] sorted: [0,30] opens room 1; [5,10] starts at 5 with 5 < 30, open room 2; [15,20] starts at 15, and rooms[0]=10 <= 15, 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.