【leetcode】56 Merge Intervals

发表于 | 分类于 ，


描述

样例

样例1

1
2
输入: [1,3],[2,6],[8,10]
输出: [1,6],[8,10]

样例2

1
2
输入:[1,4],[2,3]
输出: [1,4]

思路

先排序，后比较当前这个数的 end 和下一个数的 start，之后处理，可以直接先把当前这个数压入结果中去，之后比较。

note: cmp 比较函数写在类里面要 static , 并且要写成 a.pos < b.pos ，不可以 a.pos - b.pos

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
  static bool cmp(const Interval & a,const Interval & b){
     return a.start < b.start; // a.start - b.start will wrong
 }

    vector<Interval> merge(vector<Interval>& intervals) {
        sort(intervals.begin(),intervals.end(),cmp);
        vector<Interval> result;
        int idx = 0;

        while(idx < intervals.size()){
            int start = intervals[idx].start;
            int end = intervals[idx].end;
            idx++;
            while(idx < intervals.size() && end >= intervals[idx].start ){
                end = std::max(end,intervals[idx++].end);
            }
            result.push_back(Interval(start,end));
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<Interval> merge(vector<Interval> &intervals) {

    vector<Interval> result;

    if (intervals.size() <= 0) return result;
    //sort the inervals. Note: using the customized comparing function.
    sort(intervals.begin(), intervals.end(), compare);
    for(int i=0; i<intervals.size(); i++) { 
        int size = result.size();
        // if the current intervals[i] is overlapped with previous interval.
        // merge them together
        if( size>0 && result[size-1].end >= intervals[i].start) {
            result[size-1].end = max(result[size-1].end, intervals[i].end); 
        }else{
            result.push_back(intervals[i]);
        }
    }
    return result;
}

参考

原题链接