这几天京东零售校招的薪资爆料让我眼前一亮。图上的“31×19”，再加上硕士985的背景，属实是一发王炸了💣。
算法题：无重叠区间
思路分析
贪心的切入点
从区间的终点下手：为了让剩下的区间尽可能多，应该选择区间结束得最早的那个，留出更多的空间给后面的区间。 按终点排序：把这些区间按照它们的结束时间升序排序，这样方便我们快速找到结束最早的区间。
动手写代码
import java.util.Arrays;
public class NonOverlappingIntervals {
public static int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length == 0) return 0;
// 1. 按区间的结束时间升序排序
Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
int end = intervals[0][1]; // 初始化第一个区间的结束时间
int count = 0; // 需要移除的区间数
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] < end) {
// 当前区间的开始时间 < 前一个区间的结束时间，说明有重叠
count++;
} else {
// 没有重叠，更新结束时间
end = intervals[i][1];
}
}
return count;
}
public static void main(String[] args) {
int[][] intervals = {{1, 2}, {2, 3}, {3, 4}, {1, 3}};
System.out.println("需要移除的最少区间数: " + eraseOverlapIntervals(intervals));
}
}
怎么理解这段代码？
排序：首先我们用 Arrays.sort按结束时间给区间排了序。
比如输入 [[1, 2], [2, 3], [3, 4], [1, 3]]，排序后变成 [[1, 2], [2, 3], [1, 3], [3, 4]]。遍历：然后从头到尾扫一遍区间。
如果下一个区间的起点小于当前区间的终点，说明它俩有重叠，那就得删掉一个；但你也不能删着玩，删哪个？当然是删后面的区间（毕竟你是按结束时间排的，越靠后的区间越不友好）。 如果没重叠，就更新当前的“终点”为这个区间的结束时间。
count 加 1。举个例子走流程
排序后：[[1, 2], [2, 3], [3, 4], [1, 3]]。 第一个区间 [1, 2]，当前终点是 2。 第二个区间 [2, 3]，起点 2 >= 终点 2，没重叠，更新终点为 3。 第三个区间 [3, 4]，起点 3 >= 终点 3，没重叠，更新终点为 4。 第四个区间 [1, 3]，起点 1 < 终点 4，有重叠，删掉， count + 1。
Tips
如果面试官再问优化，思考一下能否更高效地排序，或者扩展到类似问题，比如求最大不重叠区间数。 面试的时候千万别忘了讲解思路，这段代码逻辑虽然不复杂，但面试官听你咋分析问题是关键。
对编程、职场感兴趣的同学，可以链接我，微信：coder301 拉你进入“程序员交流群”。
