Merge Intervals : https://leetcode.com/problems/merge-intervals/
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
解析：
容易想到，先按start对各区间排序，然后比较相邻的2个区间的end和start的大小，如果intervals[i].end >= intervals[i+1].start 则可以合并，但需要注意的是，如果intervals[i].end >= intervals[i+1].end，则前一个完全包含后一个，因此在判断能够合并时，还要判断存在完全包含的情况，如果不包含，才需要改变前一个的end。
e.g.
- [1, 4],[2, 3] => [1, 4]; // 容易忘记，完全包含，前一项的end不变
- [1, 4], [2, 5] => [1, 5]; // 部分重叠，后项的end覆盖前项的end
- [1, 4] [5, 6] => [1, 4], [5, 6]; // 无重叠
另外，在以下程序中，用额外空间result保存最终结果。
如果在Intervals中原位保存结果，则需要释放掉被重叠的项，我们知道vector是数组形式，每删除一项就是O(n)，因此不建议这样做（事实是，leetcode 也会超时）。
/*** Definition for an interval.* struct Interval {* int start;* int end;* Interval() : start(0), end(0) {}* Interval(int s, int e) : start(s), end(e) {}* };*/// 时间O(n)，空间O(n)
class Solution {
public:vector<Interval> merge(vector<Interval>& intervals) {if (intervals.size() <= 1)return intervals;vector<Interval> result;sort(intervals.begin(), intervals.end(), cmp);result.push_back(intervals[0]);int j = 1;while (j < size) {Interval &p = result.back();if (p.end >= intervals[j].start) {if (p.end < intervals[j].end)p.end = intervals[j].end;} else {result.push_back(intervals[j]);}j++;}return result;}
public:static bool cmp(const Interval& i1, const Interval& i2) {return i1.start < i2.start; }
};