LeetCode 253: Meeting Rooms II (Min-Heap Sweep)
LeetCode 253IntervalHeapSweep LineToday we solve LeetCode 253 - Meeting Rooms II.
Source: https://leetcode.com/problems/meeting-rooms-ii/
English
Problem Summary
Given an array of meeting intervals [start, end], return the minimum number of conference rooms required so that all meetings can be held.
Key Insight
Sort meetings by start time. Track the earliest ending ongoing meeting with a min-heap of end times.
If the next meeting starts after (or at) that earliest end, we can reuse the same room; otherwise we need a new room.
Algorithm
1) Sort intervals by start ascending.
2) For each interval [s, e]:
- While the heap top <= s, pop it (rooms freed).
- Push e into heap (occupy one room).
- Track the maximum heap size seen.
3) Maximum heap size is the answer.
Complexity Analysis
Time: O(n log n) (sorting + heap operations).
Space: O(n) in worst-case full overlap.
Common Pitfalls
- Forgetting that end == nextStart means reusable room (non-overlap).
- Updating answer only at end instead of tracking max during scan.
- Not handling empty input.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
import java.util.*;
class Solution {
public int minMeetingRooms(int[][] intervals) {
if (intervals == null || intervals.length == 0) return 0;
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
PriorityQueue<Integer> minEnd = new PriorityQueue<>();
int ans = 0;
for (int[] in : intervals) {
while (!minEnd.isEmpty() && minEnd.peek() <= in[0]) {
minEnd.poll();
}
minEnd.offer(in[1]);
ans = Math.max(ans, minEnd.size());
}
return ans;
}
}import "sort"
type MinHeap []int
func (h *MinHeap) push(x int) {
*h = append(*h, x)
i := len(*h) - 1
for i > 0 {
p := (i - 1) / 2
if (*h)[p] <= (*h)[i] {
break
}
(*h)[p], (*h)[i] = (*h)[i], (*h)[p]
i = p
}
}
func (h *MinHeap) pop() int {
a := *h
n := len(a)
top := a[0]
a[0] = a[n-1]
a = a[:n-1]
i := 0
for {
l, r := 2*i+1, 2*i+2
smallest := i
if l < len(a) && a[l] < a[smallest] { smallest = l }
if r < len(a) && a[r] < a[smallest] { smallest = r }
if smallest == i { break }
a[i], a[smallest] = a[smallest], a[i]
i = smallest
}
*h = a
return top
}
func (h MinHeap) top() int { return h[0] }
func (h MinHeap) len() int { return len(h) }
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]
})
h := MinHeap{}
ans := 0
for _, in := range intervals {
for h.len() > 0 && h.top() <= in[0] {
h.pop()
}
h.push(in[1])
if h.len() > ans { ans = h.len() }
}
return ans
}class Solution {
public:
int minMeetingRooms(vector<vector<int>>& intervals) {
if (intervals.empty()) return 0;
sort(intervals.begin(), intervals.end(),
[](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
});
priority_queue<int, vector<int>, greater<int>> pq;
int ans = 0;
for (auto& in : intervals) {
while (!pq.empty() && pq.top() <= in[0]) {
pq.pop();
}
pq.push(in[1]);
ans = max(ans, (int)pq.size());
}
return ans;
}
};import heapq
from typing import List
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
if not intervals:
return 0
intervals.sort(key=lambda x: x[0])
heap = []
ans = 0
for s, e in intervals:
while heap and heap[0] <= s:
heapq.heappop(heap)
heapq.heappush(heap, e)
ans = max(ans, len(heap))
return ansvar minMeetingRooms = function(intervals) {
if (intervals.length === 0) return 0;
intervals.sort((a, b) => a[0] - b[0]);
const heap = [];
const swap = (i, j) => ([heap[i], heap[j]] = [heap[j], heap[i]]);
const push = (x) => {
heap.push(x);
let i = heap.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (heap[p] <= heap[i]) break;
swap(p, i);
i = p;
}
};
const pop = () => {
const top = heap[0];
const x = heap.pop();
if (heap.length) {
heap[0] = x;
let i = 0;
while (true) {
let l = i * 2 + 1, r = i * 2 + 2, s = i;
if (l < heap.length && heap[l] < heap[s]) s = l;
if (r < heap.length && heap[r] < heap[s]) s = r;
if (s === i) break;
swap(i, s);
i = s;
}
}
return top;
};
let ans = 0;
for (const [start, end] of intervals) {
while (heap.length && heap[0] <= start) pop();
push(end);
ans = Math.max(ans, heap.length);
}
return ans;
};中文
题目概述
给定若干会议区间 [start, end]，求最少需要多少个会议室，才能让所有会议都能安排下。
核心思路
先按开始时间排序，然后用最小堆维护“当前占用中的会议结束时间”。
堆顶永远是最早结束的会议：如果新会议开始时间 >= 堆顶结束时间，说明可复用房间；否则必须新开房间。
算法步骤
1）按 start 升序排序。
2）遍历每个会议 [s, e]：
- 当堆顶 <= s 时持续弹出（这些会议已结束）。
- 将 e 入堆（当前会议占一个房间）。
- 用堆大小更新历史最大值。
3）历史最大堆大小即最少会议室数量。
复杂度分析
时间复杂度：O(n log n)（排序 + 堆操作）。
空间复杂度：O(n)（最坏情况下全部重叠）。
常见陷阱
- 把 end == nextStart 误判为冲突，导致房间数偏大。
- 只在最后返回堆大小，而没记录遍历过程中的最大值。
- 忘记处理空数组。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
import java.util.*;
class Solution {
public int minMeetingRooms(int[][] intervals) {
if (intervals == null || intervals.length == 0) return 0;
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
PriorityQueue<Integer> minEnd = new PriorityQueue<>();
int ans = 0;
for (int[] in : intervals) {
while (!minEnd.isEmpty() && minEnd.peek() <= in[0]) {
minEnd.poll();
}
minEnd.offer(in[1]);
ans = Math.max(ans, minEnd.size());
}
return ans;
}
}import "sort"
type MinHeap []int
func (h *MinHeap) push(x int) {
*h = append(*h, x)
i := len(*h) - 1
for i > 0 {
p := (i - 1) / 2
if (*h)[p] <= (*h)[i] {
break
}
(*h)[p], (*h)[i] = (*h)[i], (*h)[p]
i = p
}
}
func (h *MinHeap) pop() int {
a := *h
n := len(a)
top := a[0]
a[0] = a[n-1]
a = a[:n-1]
i := 0
for {
l, r := 2*i+1, 2*i+2
smallest := i
if l < len(a) && a[l] < a[smallest] { smallest = l }
if r < len(a) && a[r] < a[smallest] { smallest = r }
if smallest == i { break }
a[i], a[smallest] = a[smallest], a[i]
i = smallest
}
*h = a
return top
}
func (h MinHeap) top() int { return h[0] }
func (h MinHeap) len() int { return len(h) }
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]
})
h := MinHeap{}
ans := 0
for _, in := range intervals {
for h.len() > 0 && h.top() <= in[0] {
h.pop()
}
h.push(in[1])
if h.len() > ans { ans = h.len() }
}
return ans
}class Solution {
public:
int minMeetingRooms(vector<vector<int>>& intervals) {
if (intervals.empty()) return 0;
sort(intervals.begin(), intervals.end(),
[](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
});
priority_queue<int, vector<int>, greater<int>> pq;
int ans = 0;
for (auto& in : intervals) {
while (!pq.empty() && pq.top() <= in[0]) {
pq.pop();
}
pq.push(in[1]);
ans = max(ans, (int)pq.size());
}
return ans;
}
};import heapq
from typing import List
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
if not intervals:
return 0
intervals.sort(key=lambda x: x[0])
heap = []
ans = 0
for s, e in intervals:
while heap and heap[0] <= s:
heapq.heappop(heap)
heapq.heappush(heap, e)
ans = max(ans, len(heap))
return ansvar minMeetingRooms = function(intervals) {
if (intervals.length === 0) return 0;
intervals.sort((a, b) => a[0] - b[0]);
const heap = [];
const swap = (i, j) => ([heap[i], heap[j]] = [heap[j], heap[i]]);
const push = (x) => {
heap.push(x);
let i = heap.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (heap[p] <= heap[i]) break;
swap(p, i);
i = p;
}
};
const pop = () => {
const top = heap[0];
const x = heap.pop();
if (heap.length) {
heap[0] = x;
let i = 0;
while (true) {
let l = i * 2 + 1, r = i * 2 + 2, s = i;
if (l < heap.length && heap[l] < heap[s]) s = l;
if (r < heap.length && heap[r] < heap[s]) s = r;
if (s === i) break;
swap(i, s);
i = s;
}
}
return top;
};
let ans = 0;
for (const [start, end] of intervals) {
while (heap.length && heap[0] <= start) pop();
push(end);
ans = Math.max(ans, heap.length);
}
return ans;
};
Comments