LeetCode_057: Insert Interval

这道题就是区间插入问题，目前看到的解法主要有三种，一种是直接分析区间重叠，具有O(n)时间和O(n)空间复杂度，另一种是用二叉搜索树来做，还有一种是借助了STL库中的equal_range方法来做，写法比较优雅。这篇博客主要给出第一种解法和第三种解法的代码

题目

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].

分析区间重叠

博主的解是分析区间重叠的，速度是16ms。四个if的意思是，

1. 如果该原区间与插入区间不重叠，则将原区间保留
2. 中间两个for循环：如果该原区间与插入区间部分重叠，则将插入区间拓展，并删除原对应区间
3. 如果原区间包含了插入区间，则直接返回（因为插入和没插入效果一样）

最后要按照顺序把区间摆好，如果没有约定拜访顺序的话，输入也是要做检查的。

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) {
		vector<Interval> result;
		// check
		for (auto &interval : intervals){
			if (interval.start > newInterval.end || interval.end < newInterval.start){
				result.push_back(interval);
			} else if (interval.start < newInterval.start &&
				interval.end >= newInterval.start && interval.end <= newInterval.end){
				newInterval.start = interval.start;
			} else if (interval.start >= newInterval.start && interval.start <= newInterval.end &&
				interval.end > newInterval.end){
				newInterval.end = interval.end;
			} else if (interval.start <= newInterval.start && interval.end >= newInterval.end){
				return intervals;
			}
		}
		const int len = result.size();
		for (int i = 0; i < len; ++i){
			if (result[i].start > newInterval.start){
				result.insert(result.begin() + i, newInterval);
				return result;
			}
		}
		result.push_back(newInterval);
		return result;
	}
};

借助STL库equal_range

推荐的优雅的答案，速度12ms，核心还是equal_range方法的使用

class Solution {
public:
    vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
        auto compare = [] (const Interval &intv1, const Interval &intv2)
                          { return intv1.end < intv2.start; };
        auto range = equal_range(intervals.begin(), intervals.end(), newInterval, compare);
        auto itr1 = range.first, itr2 = range.second;
        if (itr1 == itr2) {
            intervals.insert(itr1, newInterval);
        } else {
            itr2--;
            itr2->start = min(newInterval.start, itr1->start);
            itr2->end = max(newInterval.end, itr2->end);
            intervals.erase(itr1, itr2);
        }
        return intervals;
    }
};