【LeetCode】56. 合并区间【双指针】

1.题目链接

2.解题思路 将存在交集的区间合并起来，设置当前合并区间的左边界st，右边界ed；按左边界大小对区间进行排序，遍历所有区间；设当前区间的左边界为l，右边界为r，当 ed<l 时，当前合并区间达到最大，和当前区间没有交集，即求得了一个合并后的区间[st,ed]，然后更新st=l,ed=r；当 ed>=l 时，ed更新为当前区间的右边界。

3.代码

class Solution {
          
   
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
          
   
        
        typedef pair<int,int> PII;

        vector<PII> alls;
        for(int i=0;i<(int)intervals.size();i++)
            alls.push_back({
          
   intervals[i][0],intervals[i][1]});

        sort(alls.begin(),alls.end());//排序

        int st=alls[0].first,ed=alls[0].second;
        //cout<<st<< <<ed<<endl;
        vector<PII> res;
        for(auto it:alls){
          
   
            int l=it.first,r=it.second;
            if(ed<l){
          
   
                PII mid={
          
   st,ed};
                st=l,ed=r;
                res.push_back(mid);
            }else
                ed=max(ed,r);
            //cout<<st<< <<ed<<endl;
        }

        PII left;//将最后一个区间也装入结果中
        left={
          
   st,ed};
        res.push_back(left);

        vector<vector<int>> ans;
        for(auto it:res){
          
   
            vector<int> mid;
            mid.push_back(it.first),mid.push_back(it.second);
            ans.push_back(mid);
        }

        return ans;

    }
};