[LeetCode] 56. 合并区间

[Animenzzzz]

题目描述：

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

示例 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] 可被视为重叠区间。

解题思路：首先将区间进行一次排序，之后一次遍历就行，遍历到的区间和当前res的末区间相比较，需要更新就将res弹出末尾。。继续比较，1.若比到最后res为空，直接将结果放入，跳出循环 2.若不是重叠区间，则放入，跳出循环

C++解题：

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end());
        vector<vector<int>> res;
        for (int i = 0; i < intervals.size(); i++)
        {
            if(!res.size()){
                res.push_back(intervals[i]);
            }else{
                vector<int> inte_i = intervals[i];
                while(1){
                    vector<int> tmp = res.back();
                    if(inte_i[0] <= tmp[1])//更新区间
                    {
                        tmp[1] = tmp[1] > inte_i[1] ? tmp[1]:inte_i[1];
                        res.pop_back();
                        inte_i = tmp;
                        if(!res.size()){
                            res.push_back(tmp);
                            break;
                        }
                    }
                    else //直接加入新区间
                    {
                        res.push_back(inte_i);
                        break;
                    }
                }
            }
        }
        return res;
    }
};