Merge Intervals——STL的应用

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

这里先排序，然后在合并，只要想到了先排序，这道题就好做了，运用STL中sort函数，然后自己写个比较大小的重载函数，虽然之前看到过写比较大小的重载函数，但是没自己写过，这次是自己写，是一大进步，并且之前没用过vector中的back函数，这次也是第一次用，写这个代码学到点东西~~

/**

 * 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(const Interval&a,const Interval&b)

    {

        return a.start<b.start;

    }

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

        if(intervals.size()==||intervals.size()==)

            return intervals;

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

        vector<Interval> res;

        res.push_back(intervals[]);

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

        {

            Interval temp=res.back();

            if(temp.end>=intervals[i].start&&temp.end<intervals[i].end)

            {

                 temp.end=intervals[i].end;

                 res.pop_back();

                 res.push_back(temp);

            }

            else if(temp.end<intervals[i].start)

                res.push_back(intervals[i]);

        }

        return res;

    }

};

巴特西

Merge Intervals——STL的应用

最新文章

热门文章