Merge Intervals

这个问题尝试着不去排序就”硬上弓“，用二叉树的形式去实现。最终发现霸王枪还是抵不过小李飞刀，妥协了。

下面的第一种解法就是不排序的程序，当然不排序是过不了的，加上排序就好了，但是要是用排序再如此处理就太小题大做了，就个小李飞刀嘛，关键时候用板砖就可以搞定了。

//树

bool cmpp(Interval a, Interval b)
{
	return a.start < b.start;
}
class Solution {
	struct TreeNode
	{
		Interval val;
		TreeNode *left;
		TreeNode *right;
		TreeNode(Interval a) : val(a), left(NULL), right(NULL){}
	};
public:
	void pushResult(TreeNode *root)
	{
		if(!root) return;
		if(!root->left && !root->right) {re.push_back(root->val); return;}
		//if cover the child.
		if (root->left ){
			if(root->val.start > root->left->val.end){
				re.push_back(root->val);
				//re.push_back(root->left->val);
			}
			else{
				root->left->val.start = min_2(root->val.start,root->left->val.start);
				root->left->val.end = max_2(root->val.end, root->left->val.end);
			}
			pushResult(root->left);
		}

		if(root->right){
			if(root->val.end < root->right->val.start){
				//re.push_back(root->right->val);
				re.push_back(root->val);
			}
			else{
				root->right->val.start = min_2(root->val.start,root->right->val.start);
				root->right->val.end = max_2(root->val.end,root->right->val.end);
			}
			pushResult(root->right);
		} 

	}
	int min_2(int a, int b)
	{
		return a < b ? a : b;
	}
	int max_2(int a, int b)
	{
		return b < a ? a : b;
	}
	
	vector<Interval> merge(vector<Interval> &intervals) {
		if(intervals.size() <= 1)
			return intervals;
		//build the tree
		sort(intervals.begin(), intervals.end(), cmpp);
		TreeNode *root = new TreeNode(intervals[0]);
		for (int i = 1; i < intervals.size(); ++i)
		{
			TreeNode *cur = root;
			TreeNode *pre = root;
			while (cur)
			{
				pre = cur;
				if(intervals[i].end < cur->val.start)
					cur = cur->left;
				else if(intervals[i].start > cur->val.end)
					cur = cur->right;
				else{
					cur->val.start= min_2(cur->val.start, intervals[i].start);
					cur->val.end = max_2(cur->val.end, intervals[i].end);
					break;
				}
			}
			if(!cur)
			{
				cur = new TreeNode(intervals[i]);
				if(intervals[i].end < pre->val.start)
					pre->left = cur;
				else
					pre->right = cur;
			}
		}
		//re.push_back(root->val);
		pushResult(root);
		return re;
	}
private:
	vector<Interval> re;
};

//简单的排序实现

bool cmpp(Interval a, Interval b)
{
	return a.start < b.start;
}
class Solution {
public:
int max_2( int a, int b)
{
    return a > b ? a : b;
}

vector<Interval> merge(vector<Interval> &intervals) {
    vector<Interval> re;
    sort(intervals.begin(), intervals.end(), cmpp);
    vector<Interval>::iterator it = intervals.begin();
    while(it != intervals.end()) {
        re.push_back(*it);
        ++it;
        while(it != intervals.end() && (*it).start <= re.back().end)
           {
               re.back().end = max_2(re.back().end, (*it).end);
               ++it;
           }
    }
    return re;
}
};

Merge Intervals

原文：http://blog.csdn.net/shiquxinkong/article/details/18324451