156. 合并区间先排序再处理
给出若干闭合区间，合并所有重叠的部分。 样例 给出的区间列表 => 合并后的区间列表：
[ [
[1, 3], [1, 6],
[2, 6], => [8, 10],
[8, 10], [15, 18]
[15, 18] ]
]先排序再处理
这个问题如果按照区间的开始进行排序之后就会好处理得多，如果不要求原位处理，可以新建一个vector，一个一个放入容器之中，放入的时候要判断是否有交叉或者包含的情况。这种情况写出来的程序是很简单的。这个题目要求尽量用O(1)的空间，所以借助了vector的erase函数，这个函数是一个泛型函数，在STL的容器中都可使用。简单介绍一下：
iterator erase (const_iterator position);
iterator erase (const_iterator first, const_iterator last);Erase elements Removes from the vector either a single element (position) or a range of elements ([first,last]). This effectively reduces the container size by the number of elements removed, which are destroyed. Because vectors use an array as their underlying storage, erasing elements in positions other than the vector endcauses the container to relocate all the elements after the segment erased to their new positions. This is generally an inefficient operation compared to the one performed for the same operation by other kinds of sequence containers (such as list or forward_list).
这个说的很清楚，就是删除一个元素或者一个区间的元素，有两个重载函数，对于vector这种容器来说，删除起来比list要慢得多，这个也早就讨论过，是因为后面的所有元素都要移动。如果给的是区间，遵循前闭后开原则。 返回的迭代器指向的是删除的元素后面一个元素的位置。
//这个不加静态的话lintcode编译不通过，按理说并不需要这样。
static bool cmp(const Interval &s1,const Interval &s2)
{
return s1.start<s2.start;
}
vector<Interval> merge(vector<Interval> &intervals) {
vector<Interval> res;
if(intervals.empty())
return res;
sort(intervals.begin(),intervals.end(),cmp);
//先排序
int i=0;
int sz=intervals.size();
while(i<sz-1)
{
if(intervals[i].start<=intervals[i+1].start&&intervals[i].end>=intervals[i+1].end) //后一个被前一个包含
{
intervals.erase(intervals.begin()+i+1); //把后面这个节点删掉
sz--;
}
else if(intervals[i].start<=intervals[i+1].start&&intervals[i].end>=intervals[i+1].start)
//两者有交叉
{
intervals[i].end=intervals[i+1].end;
intervals.erase(intervals.begin()+i+1); //把后面这个节点删掉
sz--;
}
else //没有重叠，去处理下一个区间
i++;
}
return intervals;
// write your code here
}腾讯云开发者
