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

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

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.

Python

def min_meeting_rooms(intervals):
    if not intervals:
        return 0
    max_end = max(e for _, e in intervals)
    best = 0
    for t in range(max_end + 1):                       # L1: T iterations
        active = sum(1 for s, e in intervals if s <= t < e)  # L2: O(n) per tick
        best = max(best, active)
    return best

TypeScript

function minMeetingRooms(intervals: number[][]): number {
    if (intervals.length === 0) return 0;
    const maxEnd = Math.max(...intervals.map(([, e]) => e));
    let best = 0;
    for (let t = 0; t <= maxEnd; t++) {                // L1: T iterations
        const active = intervals.filter(([s, e]) => s <= t && t < e).length;  // L2: O(n) per tick
        best = Math.max(best, active);
    }
    return best;
}

Go

func minMeetingRooms(intervals [][]int) int {
    if len(intervals) == 0 { return 0 }
    maxEnd := 0
    for _, iv := range intervals {
        if iv[1] > maxEnd { maxEnd = iv[1] }
    }
    best := 0
    for t := 0; t <= maxEnd; t++ {             // L1: T iterations
        active := 0
        for _, iv := range intervals {          // L2: O(n) per tick
            if iv[0] <= t && t < iv[1] { active++ }
        }
        if active > best { best = active }
    }
    return best
}

Swift

final class Solution {
    func minMeetingRooms(_ intervals: [[Int]]) -> Int {
        guard let maximum = intervals.map({ $0[1] }).max() else { return 0 }
        var answer = 0
        for time in 0...maximum { answer = max(answer, intervals.filter { $0[0] <= time && time < $0[1] }.count) }
        return answer
    }
}

Direct but quadratic in (T · n). Useful as a sanity-check oracle, never as a real solution.

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.

Python

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)

TypeScript

// Min-heap backed by a sorted array (small n). For large n use a proper heap library.
function minMeetingRooms(intervals: number[][]): number {
    intervals.sort((a, b) => a[0] - b[0]);   // L1: O(n log n)
    const heap: number[] = [];               // L2: O(1)

    const heapPush = (val: number) => { heap.push(val); heap.sort((a, b) => a - b); };
    const heapPop = () => heap.shift()!;

    for (const [s, e] of intervals) {        // L3: outer loop, n iterations
        if (heap.length > 0 && heap[0] <= s) heapPop();  // L4/L5: O(log n) free a room
        heapPush(e);                         // L6: O(log n) book a room
    }
    return heap.length;                      // L7: O(1)
}

Go

func minMeetingRooms(intervals [][]int) int {
    if len(intervals) == 0 { return 0 }
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]  // L1: O(n log n)
    })
    h := &MinHeap{}                               // L2: O(1)
    heap.Init(h)
    for _, iv := range intervals {                // L3: outer loop, n iterations
        if h.Len() > 0 && (*h)[0] <= iv[0] {
            heap.Pop(h)                           // L4/L5: O(log n) free a room
        }
        heap.Push(h, iv[1])                       // L6: O(log n) book a room
    }
    return h.Len()                                // L7: O(1)
}

Swift

final class Solution {
    func minMeetingRooms(_ intervals: [[Int]]) -> Int {
        let sorted = intervals.sorted { $0[0] < $1[0] }
        var heap = BinaryHeap<Int>(hasHigherPriority: <)
        var answer = 0
        for interval in sorted { if let end = heap.peek, end <= interval[0] { _ = heap.removeRoot() }; heap.insert(interval[1]); answer = max(answer, heap.count) }
        return answer
    }
}

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).

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

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.

Python

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)

TypeScript

function minMeetingRooms(intervals: number[][]): number {
    const starts = intervals.map(([s]) => s).sort((a, b) => a - b);  // L1: O(n log n)
    const ends   = intervals.map(([, e]) => e).sort((a, b) => a - b); // L2: O(n log n)
    let i = 0, j = 0, used = 0, best = 0;                            // L3, L4: O(1)
    while (i < intervals.length) {                                    // L5: outer loop, n iterations
        if (starts[i] < ends[j]) {                                    // L6: O(1) comparison
            used++;                                                    // L7: O(1)
            best = Math.max(best, used);                              // L8: O(1)
            i++;                                                       // L9: O(1)
        } else {
            used--;                                                    // L10: O(1)
            j++;                                                       // L11: O(1)
        }
    }
    return best;                                                       // L12: O(1)
}

Go

func minMeetingRooms(intervals [][]int) int {
    if len(intervals) == 0 { return 0 }
    starts := make([]int, len(intervals))
    ends := make([]int, len(intervals))
    for i, iv := range intervals { starts[i], ends[i] = iv[0], iv[1] }
    sort.Ints(starts)  // L1: O(n log n)
    sort.Ints(ends)    // L2: O(n log n)
    i, j, used, best := 0, 0, 0, 0  // L3, L4: O(1)
    for i < len(intervals) {         // L5: outer loop, n iterations
        if starts[i] < ends[j] {     // L6: O(1) comparison
            used++                   // L7: O(1)
            if used > best { best = used }  // L8: O(1)
            i++                      // L9: O(1)
        } else {
            used--                   // L10: O(1)
            j++                      // L11: O(1)
        }
    }
    return best                      // L12: O(1)
}

Swift

final class Solution {
    func minMeetingRooms(_ intervals: [[Int]]) -> Int {
        let starts = intervals.map { $0[0] }.sorted()
        let ends = intervals.map { $0[1] }.sorted()
        var startIndex = 0
        var endIndex = 0
        var active = 0
        var answer = 0
        while startIndex < starts.count {
            if starts[startIndex] < ends[endIndex] { active += 1; answer = max(answer, active); startIndex += 1 }
            else { active -= 1; endIndex += 1 }
        }
        return answer
    }
}

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.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

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

Python

# 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()

TypeScript

function minMeetingRooms(intervals: number[][]): number {
    intervals.sort((a, b) => a[0] - b[0]);
    const heap: number[] = [];
    const heapPush = (val: number) => { heap.push(val); heap.sort((a, b) => a - b); };
    const heapPop = () => heap.shift()!;
    for (const [s, e] of intervals) {
        if (heap.length > 0 && heap[0] <= s) heapPop();
        heapPush(e);
    }
    return heap.length;
}

console.assert(minMeetingRooms([[0,30],[5,10],[15,20]]) === 2);
console.assert(minMeetingRooms([[7,10],[2,4]]) === 1);
console.assert(minMeetingRooms([[1,5]]) === 1);
console.assert(minMeetingRooms([]) === 0);
console.assert(minMeetingRooms([[1,4],[2,5],[3,6]]) === 3);
console.assert(minMeetingRooms([[0,5],[5,10],[10,15]]) === 1);
console.log("all tests pass");

Related data structures

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

Related concepts

• Difference Arrays, range-update tactics that mark changes at boundaries and recover final values with a prefix scan.
• Intervals, range-boundary tactics for overlap, containment, scheduling, and sweep-line problems.