253. Meeting Rooms II (Medium)

Problem

Given an array of meeting time intervals, return the minimum number of conference rooms required.

Example

• intervals = [[0,30],[5,10],[15,20]] → 2
• intervals = [[7,10],[2,4]] → 1

LeetCode 253 (premium) · Link · Medium

Approach 1: Brute force, simulate time ticks

For every time t from 0 to max_end, count active meetings. Max over all t is the answer.

Complexity

• Time: O(T · n). Infeasible on big time ranges.
• Space: O(1).

Approach 2: Min-heap of end times (canonical)

Sort intervals by start. Maintain a min-heap of end times for current rooms. For each new meeting: pop end times ≤ current start (those rooms freed up); push the new end time. Answer = max heap size.

import heapq

def min_meeting_rooms(intervals):
    intervals.sort(key=lambda x: x[0])  # L1: O(n log n)
    heap = []                            # L2: O(1)
    for s, e in intervals:               # L3: outer loop, n iterations
        if heap and heap[0] <= s:        # L4: O(log n) peek
            heapq.heappop(heap)          # L5: O(log n) free a room
        heapq.heappush(heap, e)          # L6: O(log n) book a room
    return len(heap)                     # L7: O(1)

Where the time goes, line by line

Variables: n = len(intervals).

Line	Per-call cost	Times executed	Contribution
L1 (sort)	O(n log n)	1	O(n log n)
L2 (init heap)	O(1)	1	O(1)
L3 (loop)	O(1)	n	O(n)
L4 (peek)	O(1)	n	O(n)
L5 (heappop)	O(log n)	at most n	O(n log n)
L6 (heappush)	O(log n)	n	O(n log n) ← dominates
L7 (len)	O(1)	1	O(1)

L1 (sort) and L6 (n pushes) both contribute O(n log n); neither strictly dominates the other, they tie. L5 pops at most n times total across the entire loop, not once per iteration, because each interval is pushed once and popped at most once.

Complexity

• Time: O(n log n), driven by L1 (sort) and L6 (heap pushes, n total).
• Space: O(n) for the heap in the worst case (all meetings overlap).

Approach 3: Sweep line with separate start/end arrays (counters only)

Sort starts and ends independently. Two pointers; increment count on a start, decrement on an end (before a new start). Track max count.

def min_meeting_rooms(intervals):
    starts = sorted(s for s, _ in intervals)   # L1: O(n log n)
    ends   = sorted(e for _, e in intervals)   # L2: O(n log n)
    i = j = 0                                  # L3: O(1)
    used = best = 0                            # L4: O(1)
    while i < len(intervals):                  # L5: outer loop, n iterations
        if starts[i] < ends[j]:                # L6: O(1) comparison
            used += 1                          # L7: O(1)
            best = max(best, used)             # L8: O(1)
            i += 1                             # L9: O(1)
        else:
            used -= 1                          # L10: O(1)
            j += 1                             # L11: O(1)
    return best                                # L12: O(1)

Where the time goes, line by line

Variables: n = len(intervals).

Line	Per-call cost	Times executed	Contribution
L1 (sort starts)	O(n log n)	1	O(n log n) ← dominates
L2 (sort ends)	O(n log n)	1	O(n log n) ← dominates
L3, L4 (init)	O(1)	1	O(1)
L5 (loop test)	O(1)	n	O(n)
L6-L11 (body)	O(1)	n	O(n)
L12 (return)	O(1)	1	O(1)

After sorting, the while loop runs exactly n times (i advances once per iteration until i == n). Every comparison and counter update is O(1), so the loop contributes only O(n). All the cost lives in the two sorts.

Complexity

• Time: O(n log n), driven by L1 and L2 (the two sorts).
• Space: O(n) for the two auxiliary sorted arrays.

Why it works

Intuitively: whenever a meeting’s start comes before the earliest current end, we need a new room. Whenever an end arrives first, a room frees up. The running count of active rooms is exactly what we want.

Summary

Approach	Time	Space
Brute time tick	O(T · n)	O(1)
Heap of end times	O(n log n)	O(n)
Sweep-line counters	O(n log n)	O(n)

Heap version is the canonical answer. Sweep-line is the shortest.

Test cases

# Quick smoke tests, paste into a REPL or save as test_253.py and run.
# Uses the canonical implementation (Approach 2: min-heap of end times).

import heapq

def min_meeting_rooms(intervals):
    intervals.sort(key=lambda x: x[0])
    heap = []
    for s, e in intervals:
        if heap and heap[0] <= s:
            heapq.heappop(heap)
        heapq.heappush(heap, e)
    return len(heap)

def _run_tests():
    assert min_meeting_rooms([[0,30],[5,10],[15,20]]) == 2   # example 1
    assert min_meeting_rooms([[7,10],[2,4]]) == 1            # example 2: no overlap
    assert min_meeting_rooms([[1,5]]) == 1                   # single meeting
    assert min_meeting_rooms([]) == 0                        # empty
    assert min_meeting_rooms([[1,4],[2,5],[3,6]]) == 3       # all overlap
    assert min_meeting_rooms([[0,5],[5,10],[10,15]]) == 1    # touching endpoints, sequential
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

Related data structures

• Heaps / Priority Queues, end-time min-heap
• Arrays, separate start/end sorted arrays