题意分析

  • 给出若干个区间，注意这些区间的左右端点是没有顺序的，我们需要将有交集的区间进行合并，然后按照左端点的大小进行返回。

思路分析

  • 我们发现这个数组是没有顺序的，为了方便处理，我们可以先对区间进行排序，只需要按照左端点进行排序即可。排好序之后，我们对两个区间进行比较，当出现有重叠的时候就可以将区间进行合并了。我们更新合并后的左右端点。最后返回即可。

图片说明

  • 我们看上面的图，我们主要处理的是两种情况，一种是部分包含的，另一种是相交的。这两种情况的处理的方法都是不一样的。但是发现我们处理当前的区间的时候，都必须要先知道前面的那个区间的情况。所以我们可以用一个pre记录前面的那个区间。

  • 最后，我们来说一下sort排序函数，我这里用了C++和Go两种不同的写法，都是实现了结构体的部分排序，其中Go的是使用的匿名函数进行处理。

解法一 C++版

  • 代码如下
    • 需要遍历所有的区间，时间复杂度为O(n)，对区间进行了排序，时间复杂度为O(nlogn),所以取最大的时间复杂度为O(nlogn)
    • 需要对每个区间进行存储，空间复杂度为O(n) 
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
// 自定义sort排序函数
bool cmp(Interval a,Interval b){
        return a.start<b.start;
}
class Solution {
public:

    vector<Interval> merge(vector<Interval> &intervals) {
        // 先进行排序，保证是按照区间的左端点的从小到大的顺序
        sort(intervals.begin(),intervals.end(),cmp);
        vector<Interval> ans;
        Interval pre;  // 用来存储最近的一次的合并后的区间
        for(auto x:intervals) {
            // 如果区间为空，那么直接push
            if(ans.empty()){
                pre=x;
                ans.push_back(x);
            }else{
                // 否则比较这个区间的最左端和上一个区间的最右端
                if(pre.end<x.start) {
                    ans.push_back(x);
                    pre=x;
                }else{
                    // 如果存在交集那么直接合并
                    pre.end=max(pre.end,x.end);
                    ans.pop_back();
                    ans.push_back(pre);
                }
            }
        }
        return ans;
    }
};

解法二 Go语言版

  • 这种的写法注意一下如何通过匿名函数处理结构题排序和切片的使用即可。

  • 代码如下

    • 需要遍历所有的区间，时间复杂度为O(n)，对区间进行了排序，时间复杂度为O(nlogn),所以取最大的时间复杂度为O(nlogn)
    • 需要对每个区间进行存储，空间复杂度为O(n) 
package main
import . "nc_tools"
import "sort"
/*
 * type Interval struct {
 *   Start int
 *   End int
 * }
 */

/**
 * 
 * @param intervals Interval类一维数组 
 * @return Interval类一维数组
*/
func merge( intervals []*Interval ) []*Interval {
    // write code here
    // 先对切片进行排序，按照区间左端点的大小进行排序
    sort.SliceStable(intervals, func(i,j int) bool {
        if intervals[i].Start < intervals[j].Start {
            return true
        }
        return false;
    })
    var ans []*Interval
    var pre *Interval  // pre用来记录切片里面最后一个元素
    // 遍历整个切片
    for _,val := range intervals {
        // 如果这个切片为空，那么直接append
        if(len(ans)==0){
            pre=val
            ans=append(ans,val)
        } else{
            // 如果最后一个元素的区间的右端点小于当前区间的左端点，那么直接append
            if(pre.End<val.Start) {
                pre=val;
                ans=append(ans,val)
            } else{
                // 否则，更新切片的最后一个元素
                if(pre.End < val.End) {
                    pre.End=val.End
                }
                ans=ans[:len(ans)-1]
                ans=append(ans,pre)
            }
        }

    }

    return ans
}