【LeetCode】56. 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].

记返回数组为ret。

先对start排序。

然后对每两个interval（记为a,b），判断是否需要合并。

如果不需要合并（没有交集），则把a装入ret，将b继续往后。

如果需要合并（有交集），则把结果c继续往后。

这题本身是不难的，但是有两个细节：

1、compare函数中，如果是升序，必须是<而不是<=

解释：参考http://www.cplusplus.com/reference/list/list/sort/，比较必须产生strick weak ordering。

对于strick weak ordering 可以参考http://stackoverflow.com/questions/979759/operator-and-strict-weak-ordering/981299#981299

的详细说明。

总之，如果a,b不等，那么compare(a,b)和compare(b,a)其中之一为true，另一为false。

如果a,b相等，则都应该为false。

2、compare函数必须声明为静态成员函数或者全局函数，不能作为普通成员函数

解释：非静态成员函数是依赖于具体对象的，而std::sort这类函数是全局的，因此无法在sort中调用非静态成员函数。

可以把compare改成静态或者全局函数，使之不依赖于具体对象。

/**

 * 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 compare(Interval v1, Interval v2)

    {

        if(v1.start < v2.start)

            return true;

        else if(v1.start > v2.start)

            return false;

        else

            return v1.end < v2.end;

    }

    vector<Interval> merge(vector<Interval> &intervals) {

        vector<Interval> ret;

        if(intervals.empty())

            return ret;

        sort(intervals.begin(), intervals.end(), compare);

        ret.push_back(intervals[]);

        for(int i = ; i < intervals.size(); i ++)

        {//merge intervals to ret one-by-one

            //note that endv.start <= intv.start

            if(intervals[i].end <= ret[ret.size()-].end)

                //totally enclosed

                    ;

            //to here: intv.end > endv.end

            else if(intervals[i].start <= ret[ret.size()-].end)

                //merge

                ret[ret.size()-].end = intervals[i].end;

            //to here: intv.begin > endv.end

            else

                ret.push_back(intervals[i]);

        }

        return ret;

    }

};

巴特西

【LeetCode】56. Merge Intervals

最新文章

热门文章