56. Merge Intervals

题目链接

https://leetcode.com/problems/merge-intervals/

解题思路

排序+贪心

代码

bool comp(const vector<int> &a, const vector<int> &b)
{
    return a[0] < b[0];
}
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.size() <= 1) {
            return intervals;
        }

        vector<vector<int>> ans;
        sort(intervals.begin(), intervals.end(), comp);
        int s = intervals[0][0], e = intervals[0][1];
        for (int i = 1; i < intervals.size(); ++i) {
            if (intervals[i][0] > e) {
                ans.push_back({s, e});
                s = intervals[i][0];
                e = intervals[i][1];
            } else {
                e = max(e, intervals[i][1]);
            }
        }
        ans.push_back({s, e});
        return ans;
    }
};