Meeting Rooms II: Multiple Solutions and Complexity Analysis

Understanding the Problem

The Meeting Rooms II problem (LeetCode 253) asks a fundamental question: given an array of meeting time intervals intervals[i] = [start_i, end_i], what is the minimum number of conference rooms required to host all meetings without any overlap conflicts?

This is more than a coding interview staple – it models real-world resource allocation. Whether you're scheduling compute jobs on a cluster, booking conference halls, or managing overlapping user sessions, the core idea remains: how many concurrent resources do we need at peak load?

We'll explore three distinct, production-quality solutions, dissect their complexity, and highlight best practices you can apply immediately.

Approach 1: Min-Heap (Priority Queue)

The min-heap approach is the most intuitive: simulate time moving forward and keep a pool of currently active meeting end times. At each step, we free rooms whose meetings have ended, allocate a room for the incoming meeting, and track the maximum rooms ever in use.

Algorithm Steps

• Sort the intervals by start time ascending.
• Initialize a min-heap (priority queue) to store end times of ongoing meetings.
• Iterate through each meeting in sorted order:
  • While the heap’s smallest end time ≤ current meeting start, pop it (those meetings ended).
  • Push the current meeting’s end time onto the heap.
  • Update the answer: rooms_needed = max(rooms_needed, len(heap))
• Return the maximum recorded rooms needed.

Python Implementation

import heapq

def min_meeting_rooms_heap(intervals):
    # Edge case: no meetings
    if not intervals:
        return 0

    # Sort by start time
    intervals.sort(key=lambda x: x[0])

    # Min-heap for end times
    heap = []
    max_rooms = 0

    for start, end in intervals:
        # Remove meetings that have ended before this meeting starts
        while heap and heap[0] <= start:
            heapq.heappop(heap)
        # Allocate a room for the current meeting
        heapq.heappush(heap, end)
        # Track the peak number of rooms
        max_rooms = max(max_rooms, len(heap))

    return max_rooms

# Example usage
intervals = [[0, 30], [5, 10], [15, 20]]
print(min_meeting_rooms_heap(intervals))  # Output: 2

Complexity

Time: O(n log n) – sorting dominates. Each interval pushes and potentially pops from the heap, resulting in O(n log n) heap operations.
Space: O(n) for the heap, which in the worst case holds all intervals.

Approach 2: Chronological Ordering (Two Pointers)

This elegant method decouples start and end times. If we only care about how many rooms are in use at any moment, we can scan a timeline built from sorted start times and sorted end times, using two pointers.

Algorithm Steps

• Extract all start times and end times into separate arrays.
• Sort both arrays independently.
• Initialize two pointers: start_ptr = 0, end_ptr = 0, and a counter rooms_in_use = 0.
• Iterate over the sorted start times:
  • If the current start time is less than the current end time, a new meeting begins while another is still running – increment rooms_in_use and move start pointer.
  • Otherwise (start ≥ end), one meeting ends before or exactly when this one starts – decrement rooms_in_use and move end pointer.
• Keep a running maximum of rooms_in_use. Return that max.

Python Implementation

def min_meeting_rooms_two_pointers(intervals):
    if not intervals:
        return 0

    n = len(intervals)
    start_times = sorted([i[0] for i in intervals])
    end_times = sorted([i[1] for i in intervals])

    start_ptr = 0
    end_ptr = 0
    rooms_in_use = 0
    max_rooms = 0

    while start_ptr < n:
        if start_times[start_ptr] < end_times[end_ptr]:
            # A new meeting starts before the earliest ending meeting finishes
            rooms_in_use += 1
            max_rooms = max(max_rooms, rooms_in_use)
            start_ptr += 1
        else:
            # The earliest ending meeting finishes, freeing a room
            rooms_in_use -= 1
            end_ptr += 1

    return max_rooms

# Example
intervals = [[1, 5], [2, 7], [4, 9], [6, 8]]
print(min_meeting_rooms_two_pointers(intervals))  # Output: 3

Complexity

Time: O(n log n) – dominated by sorting the two arrays. The scanning loop is O(n).
Space: O(n) for the start and end arrays.

This approach often feels cleaner because it avoids a heap and uses simple pointer logic, though the underlying idea is identical to the heap method.

Approach 3: Sweep Line / Difference Array

The sweep line technique tracks “events” on the timeline. At each time point where a meeting starts, we need +1 room; where it ends, we need –1 room. By summing these deltas in chronological order, we reconstruct the room usage curve and find its peak.

Algorithm Steps

• Create a dictionary (or map) that maps a time point to the net change in required rooms.
• For each interval [start, end):
  • Increment delta at start by +1.
  • Decrement delta at end by –1 (since the room frees up at the exact end time).
• Collect all distinct time points and sort them.
• Traverse sorted time points, accumulating a running sum. The maximum sum encountered is the answer.

Python Implementation (using sorted keys)

def min_meeting_rooms_sweep_line(intervals):
    if not intervals:
        return 0

    timeline = {}
    for start, end in intervals:
        # Start event: +1 room
        timeline[start] = timeline.get(start, 0) + 1
        # End event: -1 room (room frees at `end`)
        timeline[end] = timeline.get(end, 0) - 1

    # Process events in chronological order
    rooms = 0
    max_rooms = 0
    for time in sorted(timeline.keys()):
        rooms += timeline[time]
        max_rooms = max(max_rooms, rooms)

    return max_rooms

# Example
intervals = [[0, 30], [5, 10], [15, 20]]
print(min_meeting_rooms_sweep_line(intervals))  # Output: 2

Complexity

Time: O(n log n) – sorting the unique time points. Building the delta map is O(n).
Space: O(n) for the map and sorted keys.

This method shines when intervals span a huge range but have few distinct time points, or when you need to answer queries about room usage at specific times.

Complexity Analysis & Trade-offs

All three solutions share O(n log n) time and O(n) space, but their practical performance and readability differ:

• Min-Heap: Most explicit simulation; heap operations add a small constant factor. Excellent when you need to output which room each meeting gets (by extending the logic).
• Two Pointers: Usually fastest in practice due to simple array scans and no heap overhead. Very cache-friendly.
• Sweep Line: Naturally handles interval boundaries elegantly; ideal if you later want to support queries like “how many rooms at time t?” without full re-computation.

All approaches degrade gracefully with large input sizes. The key takeaway is that the problem reduces to finding the maximum number of overlapping intervals at any point, which each method computes correctly.

Best Practices for Implementation

• Handle edge cases explicitly: Return 0 for empty input. Consider intervals with zero length (start == end) – they don’t consume a room for any measurable duration, but ensure your logic doesn’t double-count or skip them incorrectly.
• Sorting is non-negotiable: Regardless of approach, you must sort either intervals or extracted time points. Never assume input is sorted.
• Use inclusive/exclusive boundaries correctly: The problem states a meeting ends at end_i and another can start at the same time without conflict. Therefore, treat intervals as [start, end). In the heap method, pop when end_time <= start. In two pointers, use < for the start comparison. In sweep line, decrement at end, not before.
• Choose the right tool for your language: In Python, the heap solution with heapq is idiomatic. In Java, PriorityQueue or a TreeMap for sweep line fits well. In C++, std::priority_queue works, but the two-pointer method often yields simpler code.
• Keep variable names clear: max_rooms, rooms_in_use, start_ptr, etc. help during code reviews and debugging.

Conclusion

Meeting Rooms II is a classic example of transforming a scheduling problem into a maximum overlap count. Whether you choose the min-heap, two-pointer, or sweep line solution, you’re applying the same greedy insight: sort events, then scan chronologically while tracking active rooms. Mastering all three variants gives you a flexible toolkit for any interval-based resource allocation problem. Remember to always sort, respect interval boundaries, and test with edge cases. With these solutions in your repertoire, you’ll handle both interview settings and real-world scheduling systems with confidence.