[LeetCode] 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].

问题描述：给定一个区间的集合，将这些区间中有重叠的区间进行合并。

举个例子，假如要合并[a, b]和[c, d]，首先，我们将区间的第一个成员按照从小到大排列，那么a <= c，因此，需要考虑的就是b和c的大小关系。

如果b < c，那么两个区间必定不重叠，因此合并的结果就是[a, b]和[c, d]。

否则，那么两个区间必定重叠，此时，合并的第一个成员就是a，第二个成员就是max(b, d)。

/**
 * 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 Solution {
public:
    static bool cmp_func(const Interval &i1, const Interval &i2)
    {
        return i1.start < i2.start;
    }

    vector
  
    merge(vector
   
     &intervals) { vector
    
      ivec; vector
     
      ::iterator iter; if(intervals.size() == 0) return vector
      
       (); sort(intervals.begin(), intervals.end(), cmp_func); for(iter = intervals.begin(); iter + 1 != intervals.end();) { if((*iter).end < (*(iter + 1)).start) { ivec.push_back(*iter); ++iter; } else { int e = (*(iter + 1)).end; (*iter).end = max(e, (*iter).end); iter = intervals.erase(iter + 1); --iter; } } ivec.push_back(*iter); return ivec; } };
      
     
    
   
  

    static bool cmp_func(const Interval &i1, const Interval &i2)
    {
        return i1.start <= i2.start;
    }

那么上面两个排序时采用的比较函数有什么问题呢？一个是<，一个是<=，区别就在于对相等元素的比较上，使用<时排序是稳定的，使用<=时是不稳定的。不过，个人认为这应该不会对区间的合并有什么影响。无论排序是稳定的还是不稳定的，区间的第一个数字相等的区间一定都相邻放置，按道理来说，此时应该不会受稳定性的影响，比如说[1, 3] 、[1, 2]或者[1, 2]、[1, 3]的合并结果应该是一样的。所以这里还是有点疑问的。

如果真的是稳定性的问题，那么，经过如下修改，代码也是可以通过的。

1、cmp_func()使用<=版本。

2、sort()使用stable_sort版本。

实践证明，上述代码是可以AC的。

好吧！虽然还是有点不明白，不过，从这道题中可以得出下面两个编程经验：

1、比较函数最好用<或者>，而不用<=或者>=，就像默认的排序函数使用元素的operator<。

2、如果要使用<=的话，最好使用排序的稳定版本。