56. Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

 1 /**
 2  * Definition for an interval.
 3  * struct Interval {
 4  *     int start;
 5  *     int end;
 6  *     Interval() : start(0), end(0) {}
 7  *     Interval(int s, int e) : start(s), end(e) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     static bool sfun(Interval a,Interval b){ //需要用static
13         //2. sort中的比较函数compare要声明为静态成员函数或全局函数，不能作为普通成员函数，否则会报错。 invalid use of non-static member function
14 //因为：非静态成员函数是依赖于具体对象的，而std::sort这类函数是全局的，因此无法再sort中调用非静态成员函数。静态成员函数或者全局函数是不依赖于具体对象的, 可以独立访问，无须创建任何对象实例就可以访问。同时静态成员函数不可以调用类的非静态成员。
15 
16         return a.start<b.start;
17     }
18     vector<Interval> merge(vector<Interval>& intervals) {
19         vector<Interval> res;
20         if(intervals.empty()) return res;
21         
22         sort(intervals.begin(),intervals.end(),sfun);
23 
24         res.push_back(intervals[0]);
25         
26         for(int i = 1;i<intervals.size();i++)
27         {   
28             Interval pre =  res.back();////
29             Interval now = intervals[i];
30             if(now.start>pre.end)
31                 res.push_back(now);
32             else
33             {
34                 Interval ii ;
35                 ii.start = pre.start;
36                 ii.end = max(now.end,pre.end);// 注意【1,4】【2，3】 这种需要返回【1,4】所以用max
37                 res.back() = ii;
38             }
39         }
40         return res;
41     }
42 
43 };