LeetCode Insert Interval

Insert Interval

Given a set ofnon-overlappingintervals, 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 构造判断结束条件的能力。尤其是这道题看起来“简单”的题目，构造这些判断条件居然无比复杂。

这让我想起了不久前网上看到有人说他半个小时刷了8道leetcode题，我着实大吃一惊。这个世界上居然有这号人物？这样的人年薪不过百万，实在是没天理了。
但是想想这应该不可能，虽然我无法去查证，但是我做这道题的时候也在想十来分钟搞定了，因为思路就两分钟出来，但是因为各种小问题，到最后程序出来，吃透，优化好，居然搞了我几个小时。
也就是说如果做leetcode题，光写解法，不写程序的话，那么半个小时10题以上都没问题，但是如果要写出AC的程序的话，随便挑题，也不大可能半个小时8道题吧。
当然不排除有天才，如果有，麻烦证明一下给我看，让我开开眼界，O(∩_∩)O~。
下面是我认为最简洁清晰的程序了：

/**
 * 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> &v, Interval nv) 
	{
		vector<Interval> res;
		int sta = nv.start, end = nv.end;
		int i = 0;

		//注意：找到第一个起点的条件
		for (; i<v.size() && sta > v[i].end; i++)
		{
			res.push_back(v[i]);
		}

		//注意：为空或过了结尾点
		if (i<v.size())
			sta = min(sta, v[i].start);

		//注意：找到结束点的条件
		for (; i<v.size() && end >= v[i].start; i++)
			end = max(end, v[i].end);

		res.push_back(Interval(sta, end));

		res.insert(res.end(), v.begin()+i, v.end());
		
		return res;
	}
};

2014-1-29 update

锻炼了思维，本题也不是那么困难的，找到规律还要找到很好的处理方法就行。

重做了下，可以10分钟内做出来了。

vector<Interval> insert(vector<Interval> &v, Interval nv) 
	{
		vector<Interval> rs;
		int i = 0;
		for ( ; i < v.size() && v[i].end < nv.start; i++)
		{
			rs.push_back(v[i]);
		}
		if (i == v.size())
		{
			rs.push_back(nv);
			return rs;
		}
		nv.start = min(nv.start, v[i].start);

		for ( ; i < v.size() && v[i].start <= nv.end; i++)
		{
			nv.end = max(nv.end, v[i].end);
		}
		rs.push_back(nv);

		for ( ; i < v.size(); i++)
		{
			rs.push_back(v[i]);
		}
		return rs;
	}