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;}
};