leetcode 56. Merge Intervals 区间合并

骑猪看日落 2022-06-09 10:54 111阅读 0赞

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

这道题考察的是区间合并，解决方法很简单，按照区间的起始值从小到大排序，然后逐个合并即可。需要注意的地方是**合并之后一个区间。**

代码如下：

import java.util.ArrayList;
    import java.util.Comparator;
    import java.util.List;
    
    
    /*class Interval 
    {
          int start;
          int end;
          Interval() { start = 0; end = 0; }
          Interval(int s, int e) { start = s; end = e; }
    }*/
    
    public class Solution 
    {
    
        public List<Interval> merge(List<Interval> intervals)
        {       
            if(intervals==null || intervals.size()<=1)
                return intervals;   
            intervals.sort(new Comparator<Interval>() {
                @Override
                public int compare(Interval o1, Interval o2) {
                    return o1.start-o2.start;
                }
            });
    
            List<Interval> res=new ArrayList<>();
            Interval pre=intervals.get(0);
            for(int i=1;i<intervals.size();i++)
            {
                Interval now=intervals.get(i);
                if(pre.end>=now.start)
                    pre=new Interval(pre.start, Math.max(pre.end, now.end));
                else
                {
                    res.add(pre);
                    pre=now;
                }
            }
            res.add(pre);
            return res;
        }
    }

下面是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) {}
    };
    */
    
    bool cmp(Interval a, Interval b)
    {
        if (a.start < b.start)
            return true;
        else
            return false;
    }
    
    class Solution 
    {
    public:
        vector<Interval> merge(vector<Interval>& in) 
        {
            if (in.size() <= 1)
                return in;
    
            vector<Interval> res;
            sort(in.begin(),in.end(),cmp);
    
            Interval pre = in[0];
            for (int i = 1; i < in.size(); i++)
            {
                Interval now = in[i];
                if (pre.end < now.start)
                {
                    res.push_back(pre);
                    pre = now;
                }
                else
                    pre = Interval(pre.start,max(pre.end,now.end));
            }
            res.push_back(pre);
            return res;
        }
    };