Leetcode 56: 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].

本题是对interval这种数据结构进行操作，interval也是在面试中很常见的数据结构，即表示时间的起点和终点，对interval的操作，一般需要先对其进行排序，对一个interval的集合进行排序，需要overload sort的functor， 即自定义一个comp 类，overload operator()， 在sort()里面需要引入comp的一个object，这样就能实现对interval 集进行排序了， 一般可以按照start 或者end排序，排序之后再对interval进行处理就很方便了。 

interval的结构：
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */

这题对Interval按起始点排序之后，剩下就是scan 合并问题了。

 solution1 是我自己一开始做的答案，可以通过，但是588ms, 我的合并想法是用一个slow 和fast指针代表可以合并的interval区间，当没有可以合并的时候，就将这个slow.start 和 max_end插入到结果集合中，这里面就有很多的操作。比较费时。利用slow和fast指针进行操作还是要注意fast移到最后的时候，有没有遗漏没有处理的元素。

通过几次利用slow 和fast指针的使用，发现slow 和fast在使用时容易出现的错误，在于能否会忽略最后一个元素的处理，以及怎样操作slow 和 fast能够避免这样的问题出现。 
 
Solution1:
class comp {
public:
    bool operator()(Interval left, Interval right) {
        return left.start < right.start;
    }
};
class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        vector<Interval> rst;
        //sanity check
        if (intervals.size() <= 1) return intervals;
        comp mycomp;
        //sort the intervals on x
        sort(intervals.begin(), intervals.end(), mycomp);
        //find the first non ascending point
        int slow = 0;
        int fast = 0;
        int max_end = intervals[fast].end;
        while (fast < intervals.size()-1) {
            if (max_end >= intervals[fast+1].start) {
                //get the maximum end of the merged intervals
                max_end = max(max_end, intervals[fast+1].end);
                fast++;
            } else {
                Interval in(intervals[slow].start, max_end);
                rst.push_back(in);
                slow = fast + 1;
                fast++;
                max_end = intervals[fast].end;
            }
        }
        Interval in1(intervals[slow].start, max_end);
        rst.push_back(in1);
        return rst;
    }
};

solution2是我在网上看看别人有没有更好的算法的时候找到的，区别在于合并时的处理方式，这个solution很巧妙地利用结果集进行处理，先push一个interval到结果集，再intervals集合里面的元素与结果集中最后那个interval进行合并，如果可以合并，更新结果集end,如果不能合并，将新的interval插入到结果集中，这样省去了很多的操作，572ms通过。

Solution 2:

class comp {
public:
    bool operator()(Interval left, Interval right) {
        return left.start < right.start;
    }
};
class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        vector<Interval> rst;
        //sanity check
        if (intervals.size() <= 1) return intervals;
        comp mycomp;
        //sort the intervals on x
        sort(intervals.begin(), intervals.end(), mycomp);
        //find the first non ascending point
        int slow = 0;
        int fast = 0;
        rst.push_back(intervals[0]);
        for (int i = 1; i < intervals.size(); i++) {
            if (rst[rst.size()-1].end >= intervals[i].start ) {
                rst[rst.size()-1].end = max(rst[rst.size()-1].end, intervals[i].end);
            } else {
                rst.push_back(intervals[i]);
            }
        }
        return rst;
    }
};