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:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
解题思路：
1、先用两次二分查找找到和待插入的区间有关系的区间范围；
2、将有关系的区间做处理；
3、生成新的合并后的区间并返回；
解题步骤：
代码：
/**
* 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:
static bool partial_order(const Interval &a, const Interval &b) {
return a.end < b.start;
}; vector<Interval> insert(std::vector<Interval> &intervals, Interval newInterval) {
vector<Interval>::iterator less = lower_bound(intervals.begin(), intervals.end(), newInterval, partial_order);
vector<Interval>::iterator greater = upper_bound(intervals.begin(), intervals.end(), newInterval, partial_order); vector<Interval> answer;
answer.insert(answer.end(), intervals.begin(), less);
if (less < greater) {
newInterval.start = min(newInterval.start, (*less).start);
newInterval.end = max(newInterval.end, (*(greater - )).end);
}
answer.push_back(newInterval);
answer.insert(answer.end(), greater, intervals.end()); return answer;
}
};
不用lower_bound和upper_bound写的AC烂代码，留作改进：
/**
* 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) {
if (intervals.empty())
return vector<Interval> (, newInterval);
int left = ;
int right = intervals.size() - ;
int size = intervals.size();
int ins_start, ins_end; while (left < right) {
int mid = (left + right) / ;
if (intervals[mid].end < newInterval.start)
left = mid + ;
else
right = mid;
}
ins_start = left; left = left == ? : left - ;
right = intervals.size() - ;
while (left < right) {
int mid = (left + right) / + ;
if (newInterval.end < intervals[mid].start)
right = mid - ;
else
left = mid;
}
ins_end = right; if (ins_end == && newInterval.end < intervals[].start) {
intervals.insert(intervals.begin(), newInterval);
return intervals;
}
if (ins_start == size - && newInterval.start > intervals[size - ].end) {
intervals.push_back(newInterval);
return intervals;
} vector<Interval> answer;
answer.insert(answer.end(), intervals.begin(), intervals.begin() + ins_start);
if (ins_start <= ins_end) {
newInterval.start = min(newInterval.start, intervals[ins_start].start);
newInterval.end = max(newInterval.end, intervals[ins_end].end);
}
answer.push_back(newInterval);
answer.insert(answer.end(), intervals.begin() + ins_end + , intervals.end());
return answer; }
};
