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

第一反应就是先对数据进行一个简单的sort排序，然后循环比较就可以了。在实际代码中遇到一个问题就是在cmp函数中

如果将< 改为 <=   会出现超时的情况

/**
 * 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 cmp(const Interval &val1,const Interval &val2)
    {
        return (val1.start < val2.start);
    }
class Solution {
public:
  vector<Interval> merge(vector<Interval> &intervals) {
        vector<Interval> result;
        result.clear();
        if(intervals.empty())
        {
            return result;
        }
        sort(intervals.begin(),intervals.end(),cmp);
        int length = intervals.size();
        result.push_back(intervals[0]);
        
        for(int i = 1; i < length; i++)
        {
            int n = result.size();
            if((result[n-1].end >= intervals[i].start) && (result[n-1].start <= intervals[i].start))
            {
                result[n-1].end = ((result[n-1].end > intervals[i].end)? result[n-1].end:intervals[i].end);
            }
            else
            {
                result.push_back(intervals[i]);
            }
        }
        return result;
    }
};

这样会导致一个问题就是在最后一个数据的时候需要自己再单独放入到vector当中

/**
 * 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 cmp(const Interval &val1,const Interval &val2)
    {
        return (val1.start < val2.start);
    }
class Solution {
public:
  vector<Interval> merge(vector<Interval> &intervals) {
        vector<Interval> result;
        result.clear();
        if(intervals.empty())
        {
            return result;
        }
        sort(intervals.begin(),intervals.end(),cmp);
        int length = intervals.size();
        Interval mergeVal(0,0);
        mergeVal.start = intervals[0].start;
        mergeVal.end = intervals[0].end;
        if(length == 1)
        {
            result.push_back(mergeVal);
            return result;
        }
        for(int i = 1; i < length; i++)
        {
            if((mergeVal.end >= intervals[i].start) && (mergeVal.start <= intervals[i].start))
            {
                mergeVal.end = ((mergeVal.end > intervals[i].end)? mergeVal.end:intervals[i].end);
            }
            else
            {
                result.push_back(mergeVal);
                mergeVal.start = intervals[i].start;
                mergeVal.end = intervals[i].end;
            }
        }
        result.push_back(mergeVal); //<将最后一个放入
        return result;
    }
};

LeetCode—Merge Intervals

原文：http://blog.csdn.net/xietingcandice/article/details/44595251