区间调度问题是贪心算法的经典应用场景：在有限资源下选择最多的不重叠区间。从简单的活动选择到复杂的会议室分配，核心都是"排序 + 贪心选择"。
一、经典问题：最多不重叠区间
Mermaid · 渲染中（下方为源码）
graph LR A[区间集合] --> B[按结束时间排序] B --> C[贪心选最早结束] C --> D[跳过冲突]
给定 n 个区间 [start, end]，选出最多的互不重叠区间。
贪心策略：按结束时间排序
// LeetCode 435: 无重叠区间（求最少移除数）
int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[1] - b[1]); // 按结束时间
int count = 0;
int end = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] < end) {
count++; // 重叠，移除
} else {
end = intervals[i][1]; // 不重叠，保留
}
}
return count;
}为什么按结束时间？
结束越早 → 留给后续区间的空间越大 → 能选更多。
二、会议室问题（LeetCode 253）
求同时进行的最大会议数 = 最少需要的会议室数。
方法一：排序 + 最小堆
int minMeetingRooms(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]); // 按开始时间
PriorityQueue<Integer> pq = new PriorityQueue<>(); // 结束时间
for (int[] interval : intervals) {
if (!pq.isEmpty() && pq.peek() <= interval[0]) {
pq.poll(); // 复用会议室
}
pq.offer(interval[1]);
}
return pq.size();
}方法二：扫描线（事件排序）
int minMeetingRooms(int[][] intervals) {
int n = intervals.length;
int[] starts = new int[n], ends = new int[n];
for (int i = 0; i < n; i++) { starts[i] = intervals[i][0]; ends[i] = intervals[i][1]; }
Arrays.sort(starts); Arrays.sort(ends);
int rooms = 0, maxRooms = 0, endPtr = 0;
for (int i = 0; i < n; i++) {
if (starts[i] >= ends[endPtr]) {
endPtr++;
} else {
rooms++;
}
maxRooms = Math.max(maxRooms, rooms);
}
return maxRooms;
}三、区间合并（LeetCode 56）
int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> merged = new ArrayList<>();
for (int[] interval : intervals) {
if (merged.isEmpty() || merged.get(merged.size()-1)[1] < interval[0]) {
merged.add(interval);
} else {
merged.get(merged.size()-1)[1] = Math.max(merged.get(merged.size()-1)[1], interval[1]);
}
}
return merged.toArray(new int[0][]);
}四、区间调度变体
| 问题 | 策略 |
|---|---|
| 最多不重叠区间 | 按结束时间排序 + 贪心 |
| 最少移除使不重叠 | 同上（n - 最多保留） |
| 最少会议室 | 按开始排序 + 堆 |
| 区间合并 | 按开始排序 + 合并 |
| 用最少点覆盖所有区间 | 按结束排序 + 贪心放点 |
| 区间分组（LeetCode 2406） | 最少组数 = 最大重叠深度 |
用最少点覆盖所有区间
// LeetCode 452: 用最少数量的箭引爆气球
int findMinArrowShots(int[][] points) {
Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
int arrows = 1;
int end = points[0][1];
for (int i = 1; i < points.length; i++) {
if (points[i][0] > end) {
arrows++;
end = points[i][1];
}
}
return arrows;
}五、贪心正确性证明
区间调度贪心的交换论证：
- 设最优解的第一个区间为 A
- 贪心选的第一个区间为 B（结束最早）
- B.end ≤ A.end → 用 B 替换 A 不会与后续冲突
- 因此贪心解 ≥ 最优解
六、面试要点
- 按结束时间排序：区间调度的核心贪心
- 堆维护活跃区间：会议室问题
- 区间合并：按开始排序 + 判断重叠
- 交换论证：证明贪心正确性
- LeetCode：56、57、253、435、452、763、1288