原题
给出一个区间的集合，请合并所有重叠的区间。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: [[1,4],[4,5]] 输出: [[1,5]] 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
解法
思想
这道题和leetcode435-无重叠区间方法有一点类似，先排序，再处理区间。
代码
Java
class Solution {
public int[][] merge(int[][] intervals) {
if(intervals.length<2) return intervals;
Arrays.sort(intervals, (array1,array2)->{
return array1[0]-array2[0];
});
int lastIndex = 0;
int cur = 1;
List<int[]> list = new ArrayList<>();
while(cur < intervals.length){
//如果两个区间没有重叠部分，都保留
if(intervals[lastIndex][1]<intervals[cur][0]){
list.add(intervals[lastIndex]);
lastIndex = cur;
cur++;
//如果两个区间重叠，合并两个区间
}else{
intervals[lastIndex][1] = Math.max(intervals[lastIndex][1],intervals[cur][1]);
cur++;
}
}
list.add(intervals[lastIndex]);
int[][] ans = new int[list.size()][2];
for(int i = 0;i<list.size();i++){
ans[i] = list.get(i);
}
return ans;
}
}
Go（2020/07/05）
func merge(intervals [][]int) [][]int {
if len(intervals) < 2 {return intervals}
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][0]<intervals[j][0]
})
lastIndex := 0
cur := 1
var list [][]int
for cur < len(intervals){
if intervals[lastIndex][1]<intervals[cur][0]{
list = append(list, intervals[lastIndex])
lastIndex = cur
cur++
}else{
intervals[lastIndex][1] = int(math.Max(float64(intervals[lastIndex][1]), float64(intervals[cur][1])))
cur++
}
}
list = append(list, intervals[lastIndex])
return list
}
Python（2020/07/05）
class Solution(object):
def merge(self, intervals):
"""
:type intervals: List[List[int]]
:rtype: List[List[int]]
"""
if len(intervals) < 2: return intervals
intervals = sorted(intervals, key=lambda e: e[0])
lastIndex = 0
cur = 1
list = []
while cur < len(intervals):
if intervals[lastIndex][1] < intervals[cur][0]:
list.append(intervals[lastIndex])
lastIndex = cur
cur += 1
else:
intervals[lastIndex][1] = max(intervals[lastIndex][1], intervals[cur][1])
cur += 1
list.append(intervals[lastIndex])
return list
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode56-%e5%90%88%e5%b9%b6%e5%8c%ba%e9%97%b4/
