Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]]
Example 2:
Input: intervals =[[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval =[4,8]Output: [[1,2],[3,10],[12,16]] Explanation: Because the new interval[4,8]overlaps with[3,5],[6,7],[8,10].
AC code:
/**
* 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> insert(vector<Interval>& intervals, Interval newInterval) {
intervals.push_back(newInterval);
sort(intervals.begin(), intervals.end(),
[](Interval& a, Interval& b) {
return a.start < b.start;
});
vector<Interval> ans;
for (const auto interval : intervals) {
if (ans.empty() || ans.back().end < interval.start) {
ans.push_back(interval);
} else {
ans.back().end = max(ans.back().end, interval.end);
}
}
return ans;
}
};
Runtime: 12 ms, faster than 50.31% of C++ online submissions for Insert Interval.
原文：https://www.cnblogs.com/ruruozhenhao/p/9818646.html