合并区间 1

合并区间

思路：

        感觉就是一个个vector遍历？ 两两对比。若第一个的第二个元素大于下一个的第一个元素，则合并，存入答案数组即可。

         nonono  新思路 思路打开！  对于每一个区间，判断他能覆盖的最大区间在哪里，然后下一次就从这个最大区间的下一个开始遍历。当然，别忘给数组排序。

一开始代码少了这个越界判断，一直报错。

代码：

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> ans;
        sort(intervals.begin(),intervals.end());
        for(int i=0,j=i+1;i<intervals.size();)
        {   
            while(j<intervals.size()&&intervals[i][1]>=intervals[j][0])
            {
                j++;
            }
            ans.push_back({intervals[i][0],intervals[j-1][1]});
            i=j;//i从合并区间的下一个元素开始
        }
        return ans;
    }
};

开心地提交，还是报错了。

果然没有考虑周到。

i不能直接更新成j，这样会遗漏很多元素。

比如：[ [1,5],[3,12],[4,6] ] 在i=0的时候，j就到2了，随后i=j=2就不会遍历到第二个元素了。而我们知道这个时候答案应该是[1,12]。

更正：

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> ans;
        sort(intervals.begin(),intervals.end());
        for(int i=0;i<intervals.size();i++)
        {   
            int start=intervals[i][0];
            int end=intervals[i][1];
            while(i+1<intervals.size()&&end>=intervals[i+1][0])
            {
                end=max(end,intervals[i+1][1]);
                i++;
            }
            ans.push_back({start,end});
        }
        return ans;
    }
};

        

原文地址：https://blog.csdn.net/weixin_66692283/article/details/140534051

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！