Leetcode|中等|区间贪心|56. 合并区间

1 贪心算法一次遍历

• 重叠则合并
• 不重叠则添加

代码语言：javascript复制

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.empty()) return {};
        // 起始点靠前的优先排列
        sort(intervals.begin(), intervals.end(), cmp);
        vector<vector<int>> solution;
        solution.emplace_back(intervals[0]);
        for (int i = 1; i < intervals.size(); i  ) {
            // 1.重叠则合并
            if (intervals[i][0] <= solution.back()[1]) 
                solution.back()[1] = max(solution.back()[1], intervals[i][1]);
            // 2.不重叠则添加
            else solution.emplace_back(intervals[i]);
        }
        return solution;
    }
};

致谢

图片来源于「代码随想录」公众号，欢迎大家关注这位大佬的公号

遍历 公众号 算法

0 人点赞