题解 | #合并区间#
合并区间
https://www.nowcoder.com/practice/69f4e5b7ad284a478777cb2a17fb5e6a
描述
给出一组区间，请合并所有重叠的区间。
请保证合并后的区间按区间起点升序排列。
数据范围：区间组数 0 \le n \le 2 \times 10^50≤n≤2×105，区间内 的值都满足 0 \le val \le 2 \times 10^50≤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]]
注意各种全包含、半包含、边界值的判断
/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
vector<Interval> merge(vector<Interval> &intervals) {
sort(intervals.begin(), intervals.end(), [](Interval a, Interval b) {return a.start < b.start;});
vector<Interval> res;
int n = intervals.size();
int i = 0;
while (i < n-1) {
Interval tmp;
tmp.start = intervals[i].start;
tmp.end = intervals[i].end;
while (i < n-1 && (tmp.end >= intervals[i+1].start || tmp.start == intervals[i+1].start)) {
tmp.end = max(tmp.end, intervals[i+1].end);
i++;
}
res.push_back(tmp);
i++;
}
if (i == n - 1) {
res.push_back(intervals[n-1]);
}
return res;
}
};
