建设工程规范发布网站/正版搜索引擎优化
合并区间
力扣链接:合并区间
题目描述
以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。
示例
示例 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] 可被视为重叠区间。
Java代码
class Solution {public static int[][] merge(int[][] intervals) {int N = intervals.length;if (N == 1) {return intervals;}Arrays.sort(intervals, (a, b) -> a[0] - b[0]);List<Integer> list = new ArrayList<Integer>();for (int i = 1; i < N; i++) {if (intervals[i][0] <= intervals[i - 1][1]) {intervals[i][0] = Math.min(intervals[i][0], intervals[i - 1][0]);intervals[i][1] = Math.max(intervals[i][1], intervals[i - 1][1]);} else {list.add(i - 1);}}list.add(N - 1);int[][] res = new int[list.size()][2];for (int i = 0; i < res.length; i++) {res[i] = intervals[list.get(i)];}return res;
}
}
思路
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
这句话是按每一数组中的第一个数从大到小排序。
先按照所有区间的左边界排序,保证第1个区间的左边界是全局最左的,然后从第2个区间开始,判断是否需要和前一个区间合并。
策略是如果前一个区间的右边界大于等于当前区间的左边界,就需要合并,合并区间的左边界是两个区间左边界的最小值,右边界是两个区间右边界的最大值,然后将合并结果覆盖掉当前区间。
如果不需要合并,说明前一个区间是独立的,将其索引记录在一个list中,最后一个区间一定是独立的,因为最极端也就是合并成了一个区间,这个区间就是最后区间,所以把N-1位置加入到list中,list中的下标就是答案。