这个问题尝试着不去排序就”硬上弓“，用二叉树的形式去实现。最终发现霸王枪还是抵不过小李飞刀，妥协了。
下面的第一种解法就是不排序的程序，当然不排序是过不了的，加上排序就好了，但是要是用排序再如此处理就太小题大做了，就个小李飞刀嘛，关键时候用板砖就可以搞定了。
//树
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;
};
这里把它贴出来，是这里也能代表一种思路，虽然这种思路有点问题，其实也不算问题，这种做法不排序还是可以实现的，就是的花费些代价，我想的办法是将生成的树当作输入，循环的建树，知道树的规模不再减少，就说明树稳定了，也就是没有能合并的区间了，但想想，这样的话就没有查找时的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<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;
}
};