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

思路：

主要想法是先从Intervals中取出所有的int值，封装到一个Node节点中，节点里保存了他是不是起点，与之匹配的值，和自己的值等3个信息。

然后对Node类型的数组workspace进行排序。

排序策略为：1.两个点值不相等，值小的排前面。2.两个点值相等，且一个为起点，一个为终点，则起点排前面。3.两个点值相等，且都为起点，终点大的排前面。4,两个点值相等，且都为终点，起点大的排前面。这个策略能适应所有的case。比如【1,4】【4,5】按照规则2，起点的4要排在终点4的前面，这个case的正确应返回【1,5】。

排序之后，从workspace的起点开始扫描，找到一个起点就记录下他的终点值，如果下步扫描又找到一个起点，就看看他的终点值比当前终点值大的话就更新当前终点值。直到workspace数组的扫描用角标所在位置的值和终点相等，则产生一个结果Interval，存入，等待返回。

举例：

Given [1,3],[2,6],[8,10],[15,18],

则排序之后，找1的终点，为3.继续扫描，找到了2,而2只是一个起点，看看他的终点为6，比3要大，更新3为6.继续扫描找到了3，虽是一个终点但小于当前最大终点6，继续扫，找到了6，与当前最大终点重合了。说明一个组合被找到，建立【1,6】，准备返回。后面以此找到后续结果，返回。

这个方法时间复杂度为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 Node{public:	int val;	bool IsBegin;	int maxend;//另一边界值 	Node() :val(0), IsBegin(true),maxend(0){}	Node(int val,bool IsBegin){		this->val = val;		this->IsBegin = IsBegin;		maxend = 0;	}};bool cmp(Node node1,Node node2){	if (node1.val
   
    node2.maxend){				return true;			}			else{				return false;			}		}		if (node1.IsBegin == false && node2.IsBegin == false){			if (node1.maxend>node2.maxend){				return true;			}			else{				return false;			}		}	}		return false;	}class Solution {public:    vector
    
      merge(vector
     
      & intervals) {	vector
      
        result;	vector
       
        ::iterator it; 	int k = intervals.size();	Node* workspace = new Node [2*k];	for (it = intervals.begin(); it != intervals.end();it++){		Node* temp1 = new Node(it->start,true);		workspace[distance(intervals.begin(), it)*2] = *temp1;//这里复制值后，存入workspace		//cout << temp1->val<
        
         end,false); workspace[distance(intervals.begin(), it)*2+1] = *temp2; workspace[distance(intervals.begin(), it) * 2].maxend = workspace[distance(intervals.begin(), it) * 2 + 1].val; workspace[distance(intervals.begin(), it) * 2+1].maxend = workspace[distance(intervals.begin(), it) * 2].val; //cout << temp2->val<
         
          barr2){ barr2 = temp; } } } return result;}};