题解 | #合并区间#

题解一：暴力
根据题意分析出两区间的关系有如下5种关系
1、A区间包含B区间；修改方案为删除B区间即可

2、B区间包含A区间；修改方案为删除A区间即可

3、A区间交B区间，且A区间在B区间的后方；修改方案将A区间的start位置修改为B区间的start位置，删除B区间

4、A区间交B区间，且A区间在B区间的后方；修改方案将A区间的start位置修改为B区间的start位置，删除B区间

5、A区间与B区间未相交，不修改

主要思路：
1、选取一个区间；
2、遍历所有区间，判断为上述4种有交集的区间关系种的哪一种，进行合并
3、重新回到步骤1
4、结束条件，直至遍历完所有区间也没有进行合并操作

复杂度分析:
时间复杂度：,每次选取一个区间，遍历其他所有区间，两重循环，而排序为O(nlogn),所以综上总的时间复杂度为O(N^2)
空间复杂度：，在原数组上进行的操作

实现如下:

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
bool cmp(Interval a, Interval b) {
    return a.start < b.start;
}
class Solution {
public:
    vector<Interval> merge(vector<Interval> &intervals) {
    int i = 0;
    while (i<intervals.size()) {
        int flag = 0;//用于标记区间是否发生了合并
        for (int j = i + 1; j < intervals.size();++j) {
            if ((intervals[i].start<=intervals[j].start&&intervals[i].end>=intervals[j].end)) {//i区间包含了j区间
                intervals.erase(intervals.begin() + j);//删除j区间
                flag = 1;
            }
            else if ((intervals[i].start>=intervals[j].start&&intervals[i].end<=intervals[j].end)) {//j区间包含了i区间
                intervals.erase(intervals.begin() + i);//删除i区间
                flag = 1;
            }
            else if (intervals[i].start>= intervals[j].start&&intervals[i].start<= intervals[j].end){//i区间与j区间相交，且i区间在后面
                intervals[i].start = intervals[j].start;//修改i区间起始位置
                intervals.erase(intervals.begin() + j);//删除j区间
                flag = 1;
            }
            else if (intervals[i].end>= intervals[j].start&&intervals[i].end<= intervals[j].end) {//i区间与j区间相交，且i区间在前面
                intervals[i].end = intervals[j].end;//修改i区间结束位置
                intervals.erase(intervals.begin() + j);//删除j区间
                flag = 1;
            }
            //上述都没出现，证明这两个区间目前没有交集
            if (flag) { i = 0; break; }//重新开始查找
        }
        if (!flag)i++;
    }
    //满足题意的排序
    sort(intervals.begin(), intervals.end(),cmp);
    return intervals;
}
};

题解二：排序+双指针
对区间进行排序，排序规则按start从小到大，使的满足合并排序的情况缩小至题解一的1、4、5这三种情况，并且只需要修改尾部指针，如下情况
1、A区间包含B区间，不修改

2、A区间与B区间相交，修改A区间的end位置

3、A区间与B区间不相交，直接将A区间加入结果res数组，对B区间进行区间合并

主要思路：
①对区间进行排序，排序规则按start从小到大
②使用两个指针，第一个指针指向正在区间合并的位置，第二指针从前往后找可以合并的区间
③当无法合并，则存入新数组
④第一个指针指向一个新的区间转到步骤②
⑥直到第二指针到数组尾部，结束遍历

复杂度分析:
时间复杂度：,排序时间复杂度O(nlogn),第二个指针遍历整个数组时间复杂度O(n),综上所述时间复杂度为O(nlogn)
空间复杂度：，新开一个数组存新区间

实现如下：

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */

bool cmp(Interval a, Interval b) {//回调函数
    if (a.start < b.start)return true;
    else if (a.start == b.start) {
        if (a.end < b.end)return true;
        else return false;
    }
    else {
        return false;
    }
}
class Solution {
public:
    vector<Interval> merge(vector<Interval> &intervals) {
        sort(intervals.begin(), intervals.end(),cmp);//排序
        vector<Interval> res;//存结果数组
        for (int i = 0; i < intervals.size(); ++i) {//i充当第二个指针
            if (!res.size() || res.back().end<intervals[i].start) {//无法满足合并条件，新加入一个区间，res尾部充当了第一个指针
                res.push_back(intervals[i]);
            }
            else {//满足合并条件，更新end位置
                if(res.back().end<intervals[i].end){
                    res.back().end = intervals[i].end;
                }
            }
        }
        return res;//返回合并结果
    }
};