LeetCode · #253

Meeting Rooms II Solution

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

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #253 (Premium)

🏗️

Pattern

Intervals — min-heap / sweep line

Given intervals where intervals[i] = [startᵢ, endᵢ], return the minimum number of conference rooms required to hold all meetings.

Example

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2 // [0,30] conflicts with [5,10] → need 2 rooms. [15,20] fits in room freed by [5,10].

Constraints

• 1 ≤ intervals.length ≤ 10⁴

Section Two · Approach 1

Sweep Line — O(n log n)

Separate all start times (+1 event) and end times (-1 event). Sort events. Sweep through, tracking running count. The peak count is the answer.

Why it works

Each start adds a concurrent meeting, each end removes one. The maximum concurrency = rooms needed.

Java — Sweep line

 import java.util.*;
class Solution {
public int minMeetingRooms(int[][] intervals) {
int[] starts = new int[intervals.length];
int[] ends   = new int[intervals.length];
for (int i = 0; i < intervals.length; i++) {
            starts[i] = intervals[i][0];
            ends[i]   = intervals[i][1];
        }
        Arrays.sort(starts);
        Arrays.sort(ends);
int rooms = 0, e = 0;
for (int s : starts) {
if (s < ends[e]) rooms++; // new room needed else e++; // reuse freed room
}
return rooms;
    }
}

Python — Sweep line

 class Solution:
def minMeetingRooms(self, intervals: list[list[int]]) -> int:
        starts = sorted(s for s, e in intervals)
        ends = sorted(e for s, e in intervals)
        rooms = ep = 0 for s in starts:
if s < ends[ep]: rooms += 1 else: ep += 1 return rooms

Section Three · Approach 2

Min-Heap — O(n log n)

Sort by start. Use a min-heap of end times (earliest room to free). For each meeting: if its start ≥ heap's min → reuse that room (poll + push new end). Else push new end (new room).

💡 Mental model: Imagine you're a receptionist. You have a list of meetings sorted by start time and a priority board showing when each room frees up (min-heap). For each meeting: peek at the board — if the earliest-freeing room is free by now, assign that room (update its end time). Otherwise, open a new room. The heap size = rooms in use.

Algorithm

Sort intervals by start.
Min-heap of end times. Push first meeting's end.
For each subsequent meeting: if start ≥ heap.peek() → heap.poll() (reuse room).
Push current meeting's end. Heap size = rooms in use.
Return max heap size (= heap.size() at end).

🎯 When to recognize this pattern: "How many resources needed concurrently?" (rooms, servers, threads). Two classic approaches: sweep line (sort events) and min-heap (track active resource end times). Both are O(n log n). Sweep line is simpler; min-heap is more intuitive for "room allocation" reasoning.

Section Four · Trace

Visual Walkthrough

Trace for [[0,30],[5,10],[15,20]] using sweep line.

Meeting Rooms II — Sweep Line

Section Five · Implementation

Code — Java & Python (Min-Heap)

Java — Min-heap

 import java.util.*;
class Solution {
public int minMeetingRooms(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int[] iv : intervals) {
if (!heap.isEmpty() && iv[0] >= heap.peek())
                heap.poll(); // reuse room
heap.offer(iv[1]); // occupy room until end
}
return heap.size();
    }
}

Python — Min-heap

 import heapq
class Solution:
def minMeetingRooms(self, intervals: list[list[int]]) -> int:
        intervals.sort()
        heap = []
for s, e in intervals:
if heap and s >= heap[0]:
                heapq.heapreplace(heap, e) # reuse room else:
                heapq.heappush(heap, e) # new room return len(heap)

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Sweep line	O(n log n)	O(n)	Two sorted arrays; two pointers
Min-heap	O(n log n)	O(n)	Heap tracks active rooms; more intuitive for allocation

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
One meeting	`[[1,5]]`	1 room.
No overlap	`[[1,2],[3,4]]`	1 room.
All overlap	`[[1,5],[2,6],[3,7]]`	3 rooms (all concurrent at time 3).
Touching	`[[1,5],[5,10]]`	start=5 ≥ end=5 → reuse. 1 room.

⚠ Common Mistake: In the sweep-line approach, using s ≤ ends[e] instead of s < ends[e]. If a meeting starts exactly when another ends, they don't overlap — the room is free. Use strict less-than to require a new room only when the meeting truly overlaps.

← Back to Interval problems

LearningTree

LC 253 · Meeting Rooms II — Solution & Explanation | DSA Guide