BM89 合并区间

BM89 合并区间

题目描述

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

请保证合并后的区间按区间起点升序排列。

//"区间"定义
class Interval {
   int start; //起点
   int end;   //终点
}

数据范围：区间组数 0≤n≤2×1050≤n≤2×105，区间内 的值都满足 0≤val≤2×1050≤val≤2×105

要求：空间复杂度 O(n)O(n)，时间复杂度 O(nlogn)O(nlogn)

进阶：空间复杂度 O(val)O(val)，时间复杂度O(val)O(val)

示例1

输入：

[[10,30],[20,60],[80,100],[150,180]]

返回值：

[[10,60],[80,100],[150,180]]

示例2

输入：

[[0,10],[10,20]]

返回值：

[[0,20]]

注意

这道题的示例有些误导，看到的可能都是由小到大的排序，所以在编码的时候考虑的不会很全面

例如：输入：[[100, 200], [10,50], [50,90]]

所以我们应该对输入的数据按，照数组的第一个元素大小进行排序！

#include <vector>
#include <algorithm>

struct Interval {
    int start;
    int end;
    Interval(int s, int e) : start(s), end(e) {} 
};

class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        if (intervals.size() <= 1) return intervals;  // 这里如果输入的数据只有一个，那么显然输出本身
        
        // 重点：先按起始点排序
        sort(intervals.begin(), intervals.end(), 
            [](const Interval& a, const Interval& b) {
                return a.start < b.start; // 由小到大
            });
        
        vector<Interval> result;
        int current_start = intervals[0].start;
        int current_end = intervals[0].end;
        
        for (int i = 1; i < intervals.size(); ++i) {
            // 当前区间的起始节点小于等于上一个区间节点的end值，说明有重叠，那么需要合并重叠区间
            if (intervals[i].start <= current_end) {
                // 有重叠，合并区间
                current_end = max(current_end, intervals[i].end);
            } else {
                // 无重叠，添加当前区间
                result.emplace_back(current_start, current_end);
                current_start = intervals[i].start;
                current_end = intervals[i].end;
            }
        }
        
        // 添加最后一个区间
        result.emplace_back(current_start, current_end);
        
        return result;
    }
};