Meeting Rooms II - Solution & Explanation

Problem Overview: You receive a list of meeting time intervals where each interval has a start and end time. The task is to determine the minimum number of meeting rooms required so that no meetings overlap in the same room. If two meetings overlap in time, they must use different rooms.

Approach 1: Min Heap (Priority Queue) Scheduling (O(n log n) time, O(n) space)

Sort the intervals by start time using sorting. Maintain a min heap that stores the end times of meetings currently using rooms. Iterate through the sorted meetings: if the earliest ending meeting in the heap finishes before the current meeting starts, reuse that room by popping the heap. Otherwise allocate a new room by pushing the current end time. The heap size at any point represents the number of rooms in use, and the maximum size is the answer. This approach models real scheduling behavior and is the most common interview solution using a heap (priority queue).

Approach 2: Two Sorted Arrays (Sweep with Two Pointers) (O(n log n) time, O(1) extra space)

Split the intervals into two arrays: one containing all start times and the other all end times. Sort both arrays independently. Use the two pointers technique to scan them. When a meeting start time is earlier than the current end time, you need a new room, so increment the room counter and move the start pointer. When an end time occurs first, a room becomes free, so move the end pointer. The maximum number of simultaneous meetings encountered during this sweep equals the required number of rooms. This approach avoids a heap while still tracking overlaps efficiently.

Approach 3: Prefix Sum / Line Sweep (O(n log n) time, O(n) space)

Model the problem as a timeline using a sweep line technique similar to prefix sum. For each interval, record +1 at the start time and -1 at the end time. After sorting the timeline events, iterate through them while maintaining a running sum of active meetings. Each +1 increases the number of rooms in use, while -1 frees one. The maximum running sum observed during the sweep gives the minimum rooms required. This approach is conceptually clean and highlights that the core problem is counting overlapping intervals.

Recommended for interviews: The min heap solution is what most interviewers expect because it clearly demonstrates interval scheduling and efficient resource reuse. The two-pointer sweep is equally optimal and often considered the cleanest implementation. Starting with the brute-force idea of checking overlaps shows understanding, but moving to the heap or sweep-line approach demonstrates strong algorithmic thinking.