给出一个区间的集合，请合并所有重叠的区间。
示例 :
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
思路:
- 将集合按照start属性数字进行排序
- 循环合并重叠区间
- 本题难度不高,但是可优化可操作的地方很多,另外,从隔壁获取了将对象按特定属性值排序的方法,感谢一波
代码:
public List<Interval> merge(List<Interval> intervals) {
if (intervals.size() == 0)
return intervals;
Collections.sort(intervals, new Comparator<Interval>() {
public int compare(Interval a, Interval b) {
return a.start - b.start;
}
});
Interval ii, jj;
for (int i = 0; i < intervals.size(); i++) {
ii = intervals.get(i);
for (int j = i + 1; j < intervals.size(); j++) {
jj = intervals.get(j);
if (ii.end >= jj.start) {
ii.end = Math.max(jj.end, ii.end);
intervals.remove(j);
j--;
}
}
}
return intervals;
}
分析:
- 使用集合工具
Collections.sort()进行排序,此处需要手动重写comparator()方法 - 简单的双循环遍历集合,在原地进行修改
- 由于start已经升序排序好了,只需要比较ii的尾节点与jj的头结点即可,同时区间修改也只需要获取最大的尾节点
- 由于是原地修改,需要删除多余的元素,并使j--防止遍历不完整
总结:
- 对象排序方法的学习,针对int类型等各类对象属性,能够提供更多解题思路
- 简单无脑的双循环还有很多能够优化的地方,这里就不多花时间了
- 原地修改需要注意指针的变化,循环的判断逻辑,防止越界等情况
