题目描述:
以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间。
解析:
1.将数组中的区间按照起始位置排序
2.用curr数组记录当前合并的最大区间,遍历数组中的每一个区间,
如果当前区间的起始位置小于curr的终点位置,则可以继续合并,所以合并并更新curr的起始位置和终止位置。
如果当前区间的起始位置大于curr的终止位置,则无法合并。
所以将curr加入到result里,并用当前的区间替换curr值。
3.循环后判断curr的长度是否为零,若不为零,则将curr加入到result里。
4.最后返回result。
Java:
public int[][] merge(int[][] intervals) { if(intervals.length < 2) { return intervals; } Arrays.sort(intervals, (i1, i2) -> Integer.compare(i1[0],i2[0])); int[] curr = intervals[0]; ArrayList<int[]> result = new ArrayList<>(); for(int[] interval : intervals) { if(curr[1] >= interval[0]) { curr[1] = Math.max(curr[1], interval[1]); } else { result.add(curr); curr = interval; } } if(curr.length != 0) { result.add(curr); } return result.toArray(new int[result.size()][]); }
JavaScript:
var merge = function(intervals) { if(intervals.length < 2) { return intervals; } intervals.sort(function(a, b){ return a[0] - b[0]; }) let curr = intervals[0]; let result = []; for(let interval of intervals) { if(curr[1] >= interval[0]) { curr[1] = Math.max(curr[1], interval[1]); } else { result.push(curr); curr = interval; } } if(curr.length !== 0) { result.push(curr); } return result; };