题解 | #合并区间#

/**
 * 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
     */
    vector<Interval> merge(vector<Interval>& intervals) {
        // write code here
        if (intervals.empty()) return {};

        // 根据区间的起点排序，如果起点相同则按终点排序
        std::sort(intervals.begin(), intervals.end(), [](const Interval& a,
        const Interval& b) {
            return a.start < b.start || (a.start == b.start && a.end < b.end);
        });

        std::vector<Interval> merged;
        for (const auto& interval : intervals) {
            // 如果合并列表为空，或者当前区间与合并列表中最后一个区间不重叠
            if (merged.empty() || merged.back().end < interval.start) {
                merged.push_back(interval);
            } else {
                // 否则，有重叠，合并区间
                merged.back().end = std::max(merged.back().end, interval.end);
            }
        }

        return merged;
    }
};