本文共 2916 字，大约阅读时间需要 9 分钟。

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

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

//树

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
   
     merge(vector
    
      &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
     
       re;};
     
    
   

这里把它贴出来，是这里也能代表一种思路，虽然这种思路有点问题，其实也不算问题，这种做法不排序还是可以实现的，就是的花费些代价，我想的办法是将生成的树当作输入，循环的建树，知道树的规模不再减少，就说明树稳定了，也就是没有能合并的区间了，但想想，这样的话就没有查找时的log优势了，当然，没插入新的区间，发生变化的时候，去调整树也可以，但都还是不若排个序来的简单，毕业设计就做个聊天系统，干嘛非得用个oracle不是。

//简单的排序实现

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
   
     merge(vector
    
      &intervals) {    vector
     
       re;    sort(intervals.begin(), intervals.end(), cmpp);    vector
      
       ::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;}};
      
     
    
   

转载地址：http://brlji.baihongyu.com/