题解 | #合并区间#

/**
 * struct Interval {
 *  int start;
 *  int end;
 *  Interval(int s, int e) : start(start), end(e) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param intervals Interval类vector
     * @return Interval类vector
     */
    static bool cmp(const Interval& a, const Interval& b) {
        return a.start < b.start;

    }


    vector<Interval> merge(vector<Interval>& intervals) {
        // write code here
        if (intervals.size() < 2) return intervals;
        vector<Interval>ans;
        sort(intervals.begin(), intervals.end(), cmp);

        Interval temp = intervals[0];

        for (int i = 1; i < intervals.size(); i++) {
            if (temp.end >= intervals[i].start) {
                temp.start = min(temp.start, intervals[i].start);
                temp.end = max(temp.end, intervals[i].end);
            } else {
                ans.emplace_back(temp);
                temp = intervals[i];
            }
        }
        ans.emplace_back(temp);
        return ans;
    }
};

合并区间，首先排序，如何判断重叠，在有序状态下，左区间的end大于右区间的start说明有重叠，有重叠就合并，比较两个区间的边界取范围更大的。如果没有重叠，则当前区间不需要合并。