給出若干閉合區(qū)間，合并所有重疊的部分。
樣例
給出的區(qū)間列表 => 合并后的區(qū)間列表：
[ [
[1, 3], [1, 6],
[2, 6], => [8, 10],
[8, 10], [15, 18]
[15, 18] ]
]
先排序再處理
這個(gè)問題如果按照區(qū)間的開始進(jìn)行排序之后就會好處理得多，如果不要求原位處理粉捻，可以新建一個(gè)vector，一個(gè)一個(gè)放入容器之中斑芜，放入的時(shí)候要判斷是否有交叉或者包含的情況肩刃。這種情況寫出來的程序是很簡單的。這個(gè)題目要求盡量用O(1)的空間，所以借助了vector的erase函數(shù)盈包，這個(gè)函數(shù)是一個(gè)泛型函數(shù)沸呐，在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).
這個(gè)說的很清楚呢燥，就是刪除一個(gè)元素或者一個(gè)區(qū)間的元素崭添，有兩個(gè)重載函數(shù)，對于vector這種容器來說叛氨，刪除起來比list要慢得多呼渣，這個(gè)也早就討論過，是因?yàn)楹竺娴乃性囟家苿?dòng)寞埠。如果給的是區(qū)間屁置，遵循前閉后開原則。
返回的迭代器指向的是刪除的元素后面一個(gè)元素的位置仁连。
//這個(gè)不加靜態(tài)的話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) //后一個(gè)被前一個(gè)包含
{
intervals.erase(intervals.begin()+i+1); //把后面這個(gè)節(jié)點(diǎn)刪掉
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); //把后面這個(gè)節(jié)點(diǎn)刪掉
sz--;
}
else //沒有重疊饭冬，去處理下一個(gè)區(qū)間
i++;
}
return intervals;
// write your code here
}
