排序在非排序题中的妙用：区间合并与贪心
摘要
很多面试题表面上不像”排序题”，但解题的关键第一步恰恰是排序。本文讲解”区间”这一类问题——合并重叠区间（56）、插入新区间（57）、会议室安排（252/253）和最少移除的区间数（435）。这类题目的共同特征是：先按区间左端点排序，再用贪心策略线性扫描。理解为什么”排序使贪心成立”是本篇的核心。
第 1 章 为什么区间题需要排序
1.1 无序区间的困境
考虑 Merge Intervals 的原始问题：给定区间列表 [[1,3],[2,6],[8,10],[15,18]]，合并所有重叠区间。
如果区间是无序的，比如 [[8,10],[2,6],[1,3],[15,18]]，如何判断哪两个区间重叠？只能对每对区间做比较，时间 。
排序的作用：按左端点排序后，如果区间 A 和区间 B 重叠，那么 A 和 B 一定是相邻的（或距离很近的），因为不可能有一个区间 C 的左端点在 A 和 B 之间但不与其中一个重叠。
更精确地说，按左端点排序后：如果当前区间和前一个区间不重叠，那么它和更前面的所有区间也不可能重叠（因为更前面的区间左端点更小，右端点也不会比前一个区间大——如果更大，它就已经和前一个区间合并了）。
这使得一次线性扫描就足够处理所有重叠情况。
1.2 排序 + 贪心的通用模式
区间题的通用范式：
- 按左端点排序（有时也按右端点排序，取决于问题）
- 维护当前”活跃区间”，逐一扫描，贪心决策
“贪心”在这里指：每次只看当前区间和活跃区间的关系，不回头重新考虑已处理的区间。排序保证了贪心的正确性：一旦某个区间处理完，后面的所有区间都不可能和它重叠（如果当前区间已经不重叠了）。
第 2 章 LeetCode 56：合并区间
2.1 题目
LeetCode 56 - Merge Intervals（中等）
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start_i, end_i]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间.
2.2 算法设计
排序：按左端点升序排序，
线性扫描：维护”当前合并区间”的右端点 curEnd，依次处理每个区间：
- 如果当前区间的左端点
start <= curEnd（重叠），将curEnd更新为max(curEnd, end)（扩展当前合并区间） - 如果
start > curEnd（不重叠），将当前合并区间加入结果，开始新的合并区间
public int[][] merge(int[][] intervals) {
// 按左端点排序
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> merged = new ArrayList<>();
int curStart = intervals[0][0];
int curEnd = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
int start = intervals[i][0];
int end = intervals[i][1];
if (start <= curEnd) {
// 重叠：扩展当前合并区间
curEnd = Math.max(curEnd, end);
} else {
// 不重叠：保存当前合并区间，开始新区间
merged.add(new int[]{curStart, curEnd});
curStart = start;
curEnd = end;
}
}
// 不要忘记最后一个合并区间
merged.add(new int[]{curStart, curEnd});
return merged.toArray(new int[0][]);
}时间 （排序），空间 （结果列表）。
2.3 合并区间的不变量
循环不变量：在每次循环开始时，merged 列表中的所有区间已经完全合并（无重叠），且都在 [curStart, curEnd] 的左边。
每次迭代后：
- 如果重叠，
[curStart, curEnd]扩展，不变量仍然成立 - 如果不重叠，
[curStart, curEnd]加入merged，新的[curStart, curEnd]从intervals[i]开始，不变量成立
生产避坑：最后一个区间一定要单独处理
循环结束时，最后的
[curStart, curEnd]还没有加入merged。很多人写完循环就直接返回，漏掉了这一步，导致最后一个（组）区间丢失。
第 3 章 LeetCode 57：插入区间
3.1 题目
LeetCode 57 - Insert Interval（中等）
给你一个无重叠的，按照区间起始端点排序的区间列表 intervals，在列表中插入一个新的区间 newInterval（如果有必要的话，先合并该区间），然后返回插入后的区间列表（同样按区间起始端点排序）。
输入: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出: [[1,2],[3,10],[12,16]]
解释: 新区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠，因此合并为 [3,10]。
3.2 三段式处理
输入已经是有序且无重叠的区间列表，新插入 newInterval，处理分三段：
- 所有在
newInterval左边且不相交的区间（end < newInterval.start）：直接加入结果 - 所有与
newInterval重叠的区间（start <= newInterval.end）：合并到newInterval - 所有在
newInterval右边且不相交的区间（start > newInterval.end）：直接加入结果
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> result = new ArrayList<>();
int i = 0, n = intervals.length;
// 第一段：所有在 newInterval 左边的区间
while (i < n && intervals[i][1] < newInterval[0]) {
result.add(intervals[i]);
i++;
}
// 第二段：合并所有与 newInterval 重叠的区间
while (i < n && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
i++;
}
result.add(newInterval); // 加入合并后的 newInterval
// 第三段：所有在 newInterval 右边的区间
while (i < n) {
result.add(intervals[i]);
i++;
}
return result.toArray(new int[0][]);
}时间 ，空间 。 这道题不需要排序（输入已有序），直接线性扫描即可。
3.3 边界条件分析
两个区间是否重叠的判断：区间 [a, b] 和 [c, d] 重叠，当且仅当 a <= d && c <= b。
- 不重叠的条件是
b < c（第一个在左）或d < a（第二个在左） - 取反：重叠是
!(b < c || d < a)=b >= c && d >= a，即a <= d && c <= b
在代码中：
intervals[i][1] < newInterval[0]：第 个区间在newInterval左边，不重叠（第一段条件）intervals[i][0] <= newInterval[1]：取反后，第 个区间的左端点<= newInterval的右端点，加上之前已经排除了”在左边不重叠”的情况，所以这里的条件就是”重叠”（第二段条件）
第 4 章 会议室问题：贪心的双面
4.1 LeetCode 252：会议室 I（能否参加所有会议）
题目：
LeetCode 252 - Meeting Rooms（简单）
给定一个会议时间安排的数组 intervals，每个会议时间都会包括开始和结束的时间 [s_i, e_i]，请你判断一个人是否能够参加这里面的全部会议。
输入: intervals = [[0,30],[5,10],[15,20]]
输出: false（[0,30] 和 [5,10] 冲突）
输入: intervals = [[7,10],[2,4]]
输出: true
解法：按开始时间排序，依次检查相邻区间是否重叠（前一个的结束时间 > 后一个的开始时间）。
public boolean canAttendMeetings(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] < intervals[i-1][1]) return false;
}
return true;
}4.2 LeetCode 253：会议室 II（最少需要多少会议室）
题目：
LeetCode 253 - Meeting Rooms II（中等）
给你一个会议时间安排的数组 intervals，每个会议时间都会包括开始和结束的时间，为避免会议冲突，同时要考虑充分利用会议室资源，请你计算所需要的最少的会议室数量。
输入: intervals = [[0,30],[5,10],[15,20]]
输出: 2
输入: intervals = [[7,10],[2,4]]
输出: 1
分析：同一时刻有几个会议在进行，就需要几个会议室。“最少会议室数”等于”某一时刻最多有多少个会议同时进行”。
解法一：最小堆（正统解法）
按开始时间排序，用最小堆维护所有正在进行的会议的结束时间：
- 如果新会议开始时，堆顶的会议已经结束（
heap.peek() <= newMeeting.start），将堆顶弹出（复用会议室），加入新会议的结束时间 - 否则，需要一个新会议室，直接加入新会议的结束时间
堆的大小就是需要的会议室数量。
public int minMeetingRooms(int[][] intervals) {
if (intervals.length == 0) return 0;
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
// 最小堆，存放各会议室的"最早空闲时间"（即当前会议的结束时间）
PriorityQueue<Integer> endTimes = new PriorityQueue<>();
for (int[] interval : intervals) {
// 如果最早空闲的会议室已经空出来了，复用
if (!endTimes.isEmpty() && endTimes.peek() <= interval[0]) {
endTimes.poll();
}
// 安排这个会议（新会议室，或复用的会议室）
endTimes.offer(interval[1]);
}
return endTimes.size();
}解法二：双数组排序（差分数组思想）
分别对所有”开始时间”和”结束时间”排序，用两个指针模拟时间推进：
- 当一个开始事件发生时，当前在用的会议室
+1 - 当一个结束事件发生时，当前在用的会议室
-1 - 记录最大值
public 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, endPtr = 0;
for (int i = 0; i < n; i++) {
if (starts[i] < ends[endPtr]) {
rooms++; // 新会议开始，需要一个新房间
} else {
endPtr++; // 有会议结束，复用房间
}
}
return rooms;
}两种解法时间都是 ，双数组解法代码更简洁，面试中两种都可以，推荐最小堆解法（更直观，更容易解释）。
第 5 章 LeetCode 435：无重叠区间（最少移除数）
5.1 题目
LeetCode 435 - Non-overlapping Intervals（中等）
给定一个区间的集合 intervals，其中 intervals[i] = [start_i, end_i]。返回需要移除区间的最小数量，使剩余区间互不重叠。
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1（移除 [1,3] 后，剩下的区间互不重叠）
输入: intervals = [[1,2],[1,2],[1,2]]
输出: 2（需要移除两个 [1,2]）
输入: intervals = [[1,2],[2,3]]
输出: 0（两个区间不重叠）
5.2 贪心策略：保留尽可能多的不重叠区间
最少移除 = 总数 - 最多可保留的不重叠区间数。问题转化为：最多能保留多少个互不重叠的区间？
这是一个经典的”活动选择问题”（Activity Selection Problem）。贪心策略：按结束时间排序，优先选结束早的区间。
为什么按结束时间排序而不是开始时间？
直觉上，结束早的区间给后面的区间留出了更多空间，更”不占地方”，更值得保留。
严格证明（交换论证）：假设某个最优解不选结束最早的区间 ，而选了某个结束更晚的区间 （ 与 有重叠）。将解中的 替换为 ，由于 结束更早， 不会与解中其他区间产生更多冲突（ 的右端 的右端，凡是不与 冲突的区间，也不会与 冲突）。因此，这个替换方案同样有效，且选了结束最早的区间 。由此，总存在一个包含”结束最早的区间”的最优解。数学归纳法推广到所有区间。
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length == 0) return 0;
// 按结束时间排序
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
int count = 1; // 保留的区间数，初始为 1（第一个区间一定保留）
int lastEnd = intervals[0][1]; // 上一个保留的区间的结束时间
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] >= lastEnd) {
// 不重叠，可以保留
count++;
lastEnd = intervals[i][1];
}
// 重叠，跳过（即"移除"这个区间）
}
return intervals.length - count;
}时间 （排序），空间 。
5.3 活动选择问题的贪心正确性总结
| 问题 | 排序维度 | 贪心策略 | 原因 |
|---|---|---|---|
| 最多活动数（活动选择） | 按结束时间升序 | 优先选结束早的 | 结束早，给后面留更多空间 |
| 最少会议室数 | 按开始时间升序 | 复用最早空出的会议室 | 最早空出的会议室最灵活 |
| 最少移除区间数 | 按结束时间升序 | 保留结束早的，移除重叠的 | 等价于最大活动选择 |
第 6 章 区间题常见变体与陷阱
6.1 端点相邻算重叠吗？
不同题目对”重叠”的定义不同：
- LeetCode 56（合并区间）：
[1,3]和[3,5]算重叠（合并为[1,5]）。代码中判断条件是start <= curEnd（使用<=） - LeetCode 435（无重叠）：
[1,2]和[2,3]不算重叠（可以共享端点）。代码中判断保留条件是start >= lastEnd（使用>=）
读题时一定要确认端点相邻是否算重叠！
6.2 排序的比较器写法
// 按左端点升序，左端点相同按右端点升序（稳定）
Arrays.sort(intervals, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
// 只按左端点升序（右端点不管）
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
// 只按右端点升序
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);注意：比较器中的 a[0] - b[0] 写法，当值非常大（如 ）时可能整数溢出，安全写法是 Integer.compare(a[0], b[0])。
6.3 LeetCode 56 的一个陷阱
考虑 [[1, 10], [2, 3], [4, 5]]，按左端点排序后已是这个顺序。
第一个区间：[1, 10]，curStart=1, curEnd=10
第二个区间：[2, 3]，2 <= 10，重叠，curEnd = max(10, 3) = 10（不缩小！）
第三个区间：[4, 5]，4 <= 10，重叠，curEnd = max(10, 5) = 10
结果：[[1, 10]]
注意 curEnd = max(curEnd, end)，不是直接 curEnd = end。如果漏掉 max，会把大区间的右端点缩小到小区间的右端点，结果错误。
小结
本文讲解了”排序 + 贪心”在区间问题中的应用：
-
Merge Intervals（56）：按左端点排序，一次扫描维护当前合并区间，遇到不重叠就保存并开始新区间。时间 。
-
Insert Interval（57）：三段式处理（左不重叠 + 合并 + 右不重叠），不需排序，线性 。
-
Meeting Rooms I（252）：排序后检查相邻区间是否重叠，。
-
Meeting Rooms II（253）：按开始时间排序 + 最小堆维护会议室结束时间，。
-
Non-overlapping Intervals（435）：按结束时间排序 + 贪心保留结束早的区间，等价于最大活动选择问题，。
区间题的核心思路：排序让贪心成立（排序后局部决策不会影响全局最优性），贪心让线性扫描足够（每次只需看当前区间与上一个的关系）。
上一篇：07 快速选择与 TopK 问题：期望 O(n) 的奇妙算法 下一篇：09 计数排序与基数排序：线性时间排序的边界与代价