首页 > 代码库 > Merge Intervals

Merge Intervals

2024-08-04 03:35:22   216人阅读

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

思路：首先以start排序，至于使用algorithm中的sort，需要自定义比较函数。可以参考：http://bbs.csdn.net/topics/340143411和http://bbs.csdn.net/topics/80039846，不过我在其中比较的时候加入了等号之后出现错误：

I use the sort function to sort the starting points of all intervals,

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

However, when I am trying to use

bool compareInterval(Interval a, Interval b){    return (a.start<=b.start);}

the compiler outputs some Runtime error, however, the compiler accepts the code if I use

bool compareInterval(Interval a, Interval b){    return (a.start<b.start);}

可以看看：https://oj.leetcode.com/discuss/10936/sort-function-problems

 

C++代码实现：

#include<iostream>#include<vector>#include<algorithm>using namespace std;struct Interval{    int start;    int end;    Interval():start(0),end(0) {}    Interval(int s,int e):start(s),end(e) {}};class Solution{public:    vector<Interval> merge(vector<Interval> &intervals)    {        if(intervals.empty())            return vector<Interval>();        if(intervals.size()==1)            return intervals;        sort(intervals.begin(),intervals.end(),Solution::mycompare);        Interval temp=intervals[0];        vector<Interval> ret;        int i;        for(i=1;i<(int)intervals.size();i++)        {            if(temp.end<intervals[i].start)            {                ret.push_back(temp);                temp=intervals[i];            }            else                temp.end=max(temp.end,intervals[i].end);        }        ret.push_back(temp);        return ret;    }    //注意，为什么要使用static呢？因为sort不是成员函数，不能直接调用类中的成员函数需要类的对象或类来调用，也可以将比较函数定义在类的外面成为非成员函数    //还有就是不能加入等号，因为sort是严格递增的    static bool mycompare(const Interval &a,const Interval &b)    {        return a.start<b.start;    }};int main(){    Solution s;    Interval a1(1,3);    Interval a2(2,6);    Interval a3(8,10);    Interval a4(15,18);    vector<Interval> intervals={a4,a3,a1,a2};    vector<Interval> result=s.merge(intervals);    for(auto a:result)        cout<<"[ "<<a.start<<" , "<<a.end<<" ]"<<endl;}

运行结果：

 

Merge Intervals


联系
我们