056 - Merge Intervals

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

Hide Tags

Array Sort

Hide Similar Problems

(H) Insert Interval

 

先按照起点排序，再扫描排序后的结果，

因为起点都排过序了，所以后一个的start肯定不会更小，那么只需要处理两种情况：

1. 后面的start，小于前一个的终点，

    此时如果后一个的end大于前一个的end，就扩大前一个的end，否则略过；

2. 后面的start，大于前一个的终点，

    这就意味着出现不连续的情况了，那么只需要push一个新的struct到结果里，

    再重复这些步骤就好了。

另外要写个排序规则。

 

/**
* Definition for an interval.
* struct Interval {
*     int start;
*     int end;
*     Interval() : start(0), end(0) {}
*     Interval(int s, int e) : start(s), end(e) {}
* };
*/
bool cmp1(Interval a, Interval b)
{
    return (a.start)<(b.start);
}

class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        vector<Interval> rst;
        int sz=intervals.size();
        if(sz)
        {
            sort(intervals.begin(), intervals.end(), cmp1);

            int done=0;
            rst.push_back(intervals[0]);
            for(int ii=1; ii<sz; ++ii)
            {
                while((ii<sz)&&((rst[done].end)>=(intervals[ii].start)))
                {
                    if((rst[done].end)<(intervals[ii].end))
                        rst[done].end = intervals[ii].end;
                    ii++;
                }
                if(ii<sz)
                {
                    rst.push_back(intervals[ii]);
                    done++;
                }
            }
        }       
        return rst;       
    }
};

 

起初还想过双排序，直觉双排序能带来更多的好处，

先按照每一对的起点排序，再按终点排序，然后对位合并，

然后分析，每个位置取两个结果的最大范围；

再然后才是扫描分析结果，更新end或者push新的struct，

后来发现其实完全不必要，因为分析的时候起点都是取两次排序里小的那个，

所以实际上只要一次排序就够了。

但郁闷的是，删掉了一次排序，以及一次vector复制，居然时间没啥变化。。。

（用临时变量替换 (rst[done].end) 之后提高了12ms，注意，done++之后也要更新临时变量）