原题

给出一个区间的集合，请合并所有重叠的区间。

示例 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/