爱悠闲 > Merge Intervals - LeetCode

Merge Intervals - LeetCode

分类: leetcode  |  标签: leetcode  |  作者: shi562217697 相关  |  发布日期 : 2015-09-28  |  热度 : 139°

一道不需要算法的问题,但是难度仍未hard,可能就是边界条件太多了,采用循环不变量就能轻松解决。

1.排序
2.对每一个interval做操作,循环中[left,right]表示当前要输出的interval,如果新的interval与当前的没有重叠,就将当前的输出,并把新的[left,right]设为新的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) {}
 * };
 */
class Solution {
    static bool cmpFun(const Interval& i1,const Interval& i2) {
        return i1.start < i2.start;
    }
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        int size = intervals.size();
        vector<Interval> ret;
        if (0 == size)
            return ret;
        //todo sort
        sort(intervals.begin(),intervals.end(),cmpFun);

        int left,right;
        for (int i = 0 ; i < size ; ++i) {
            if (0 == i) {
                left = intervals[0].start;
                right = intervals[0].end;
                continue;
            }
            if (intervals[i].start <= right)
                right = max(right,intervals[i].end);
            else {
                ret.push_back(Interval(left,right));
                left = intervals[i].start;
                right = intervals[i].end;
            }
        }
        ret.push_back(Interval(left,right));
        return ret;
    }
};

版权声明:本文为博主原创文章,未经博主允许不得转载。