LeetCode：合并区间

梦里梦外; 2021-11-16 14:24 345阅读 0赞

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

> 来源：力扣（LeetCode） 链接：[https://leetcode-cn.com/problems/merge-intervals][https_leetcode-cn.com_problems_merge-intervals]

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

排序AC代码：一遍就A掉了，但效率不高。

class Solution {
    public:
        static bool cmp(vector<int> x,  vector<int> y)
        {
            if(x[1] < y [1])
                return true;
            if(x[1] == y [1])
            {
                if(x[0] < y [0])
                    return true;
                return false;
            }
            return false;
        }
        vector<vector<int>> merge(vector<vector<int>>& intervals) {
            vector<vector<int>> res;
            if(intervals.size() <= 1)
                return intervals;
            sort(intervals.begin(), intervals.end(), cmp);
            int i = intervals.size()-1;
            int j = i - 1;
            while( j >= 0)
            {
                if(intervals[i][0] <= intervals[j][1])
                {
                    int y = intervals[i][1];
                    int x = min(intervals[j][0], intervals[i][0]);
                    intervals[i][0] = x;
                    intervals[i][1] = y;
                }
                else
                {
                    res.push_back(intervals[i]);
                    i = j;
                }
                j--;
            }
            res.push_back(intervals[i]);
            return res;
        }
    };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1VwX2p1bmlvcg_size_16_color_FFFFFF_t_70]

[https_leetcode-cn.com_problems_merge-intervals]: https://leetcode-cn.com/problems/merge-intervals
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1VwX2p1bmlvcg_size_16_color_FFFFFF_t_70]: /images/20211116/c61a33ad29a94e7eb6e6fd647ff47a23.png