LeetCode56.合并区间
题目描述
给出一个区间的集合，请合并所有重叠的区间。
示例 1:
- 输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
- 输出: [[1,6],[8,10],[15,18]]
- 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
- 输入: intervals = [[1,4],[4,5]]
- 输出: [[1,5]]
- 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
解法：贪心
本题的本质其实还是判断重叠区间问题
这几道题都是判断区间重叠，区别就是判断区间重叠后的逻辑，本题是判断区间重贴后要进行区间合并。
所以一样的套路，先排序，让所有的相邻区间尽可能的重叠在一起，按左边界，或者右边界排序都可以，处理逻辑稍有不同。
按照左边界从小到大排序之后，如果 intervals[i][0] <= intervals[i - 1][1] 即intervals[i]的左边界 <= intervals[i - 1]的右边界，则一定有重叠。（本题相邻区间也算重贴，所以是<=）
并且我们还要返回一下区间的开始和结束，所以我们需要定义两个start 和 end变量
其实就是用合并区间后左边界和右边界，作为一个新的区间，加入到result数组里就可以了。如果没有合并就把原区间加入到result数组。
代码实现
class Solution {
public int[][] merge(int[][] intervals) {
int len = intervals.length;
if (len == 1) return intervals;
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
LinkedList<int[]> list = new LinkedList<>();
int start = intervals[0][0];
int end = intervals[0][1];
for (int i = 1; i < len; i++) {
if (end >= intervals[i][0]) {
end = Math.max(end, intervals[i][1]);
}else {
int[] arr = {start, end};
list.add(arr);
start = intervals[i][0];
end = intervals[i][1];
}
}
if (list.size() == 0 | | list.getLast()[1] != intervals[len-1][1]) {
int[] arr = {start, Math.max(intervals[len-1][1], end)};
list.add(arr);
}
return list.toArray(new int[0][]);
}
}