57. Insert Interval
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].思路：找出与插入的区间不重合的(分为左右两部分)，然后再处理重合的与插入的区间。
vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) { vector<Interval> left, right; for (auto it : intervals) { if (it.end < newInterval.start) left.push_back(it); if (it.start > newInterval.end) right.push_back(it); } if (left.size() + right.size() != intervals.size()) { newInterval.start = min(newInterval.start, intervals[left.size()].start); newInterval.end = max(newInterval.end, intervals[intervals.size() - right.size() - 1].end); } left.push_back(newInterval); left.insert(left.end(), right.begin(), right.end()); return left; }其中找不重合的区间可以使用二分法。利用upper_bound.
class Solution { private: int upper_bound(const vector<Interval> &intervals, int target) { int count = intervals.size(), first = 0; while (count > 0) { int pos = first + count / 2; if (target >= intervals[pos].start) first = ++pos, count -= (count / 2 + 1); else count /= 2; } return first; } public: vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) { int N = intervals.size(); vector<Interval> res; int left = upper_bound(intervals, newInterval.start); int right = upper_bound(intervals, newInterval.end); if (left > 0 && intervals[left - 1].end >= newInterval.start && intervals[left - 1].start < newInterval.start) newInterval.start = intervals[left - 1].start; if (right > 0 && intervals[right - 1].start <= newInterval.end && intervals[right - 1].end > newInterval.end) newInterval.end = intervals[right - 1].end; for (int i = 0; i < left - 1; res.push_back(intervals[i++])); if (left > 0 && intervals[left - 1].end < newInterval.start) res.push_back(intervals[left - 1]); res.push_back(newInterval); for (int i = right; i < N; res.push_back(intervals[i++])); return res; } };