[LeetCode]Insert Interval

题目链接

因为给定的list中的interval都是sorted并且不想交的，我们可以遍历所有list当中的interval：

• 如果不和newInterval相交，直接推入结果集
• 否则，更新新的merge的interval的start和end

newInterval注意插入对应的位置即可。时间复杂度O(n)，代码如下:

	/**
	* 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) {
	int len = intervals.size();
	bool inserted = false;
	vector<Interval> res;
	for(int i = 0; i < len; ++i)
	{
	auto curr = intervals[i];
	if(curr.end < newInterval.start)res.push_back(curr);
	else if(curr.start > newInterval.end)
	{
	if(!inserted)
	{
	res.push_back(newInterval);
	inserted = true;
	}
	res.push_back(curr);
	}
	else
	{
	newInterval.start = min(newInterval.start, curr.start);
	newInterval.end = max(newInterval.end, curr.end);
	}
	}
	if(!inserted)res.push_back(newInterval);
	return res;
	}
	};

view raw Insert Interval_1.cpp hosted with ❤ by GitHub

既然list是sorted，我们以可以利用这个性质。对于newInterval = [s, e]，我们可以二分找出大于等于s的最小end对应的interval i1和小于等于end的最大start对应的interval i2，这样从i1到i2所有的interval都是应该和newInterval进行merge的。这样的话时间复杂度为O(log n + k)，k为和newInterval相交的interval的数量。注意实现的时候为了找上界和下界的时候共用一套代码，我们找的是下界的下一个数。代码如下：

	/**
	* 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) {
	int len = intervals.size(), lo = 0, hi = len - 1;
	if(intervals.empty() || intervals.back().end < newInterval.start){intervals.push_back(newInterval); return intervals;};
	int head = find(intervals, newInterval.start, 0, len - 1, true), tail = find(intervals, newInterval.end, 0, len, false) - 1;
	vector<Interval> res;
	for(int i = 0; i < head; ++i)res.push_back(intervals[i]);
	Interval mergedInterval(min(intervals[head].start, newInterval.start), max(intervals[tail].end, newInterval.end));
	res.push_back(mergedInterval);
	for(int i = tail + 1; i < len; ++i)res.push_back(intervals[i]);
	return res;
	}
	private:
	int find(vector<Interval>& intervals, int target, int lo, int hi, bool isHead)
	{
	while(lo < hi)
	{
	int mid = lo + (hi - lo) / 2;
	int curr = isHead? intervals[mid].end: intervals[mid].start;
	if(isHead)
	{
	if(curr >= target)hi = mid;
	else lo = mid + 1;
	}
	else
	{
	if(curr <= target)lo = mid + 1;
	else hi = mid;
	}
	}
	return lo;
	}
	};

view raw Insert Interval_2.cpp hosted with ❤ by GitHub