【牛客题霸题解】合并区间

首先我们来考虑一个问题：什么样的两个区间可以合并？

像上图这样，起点大的那个区间（[13，16]）的起点在另一个区间的范围之内，这样两个区间就可以进行合并了

所以我们把全部的区间按起点进行排序，然后看一下第i个区间能不能和i-1个区间合并，如果能合并的话，就删掉第i-1个区间，然后把第i个区间变成这两个区间的合并

c++

#include<algorithm>
bool cmp(Interval  a,Interval  b)
{
    if(a.start==b.start){ return a.end< b.end;}
    return a.start < b.start;
}

class Solution {
public:
    vector<Interval> merge(vector<Interval> &intervals) {
        vector<Interval> ans;
        sort(intervals.begin(),intervals.end(),cmp);
        int len = intervals.size();
        if(len==0)return intervals;
        for(int i = 1 ; i < len ; i++)
        {
                if(intervals[i].start <= intervals[i-1].end)
                {
                    intervals[i].start = min(intervals[i-1].start,intervals[i].start);
                    intervals[i].end = max(intervals[i-1].end,intervals[i].end);
                }
                else{
                        ans.push_back(intervals[i-1]);
                }
        }
        ans.push_back(intervals[len-1]);
        return ans;

    }
};

java

import java.util.*;
public class Solution {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        Collections.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval a, Interval b) {
                return a.start - b.start;
            }
        });
        ArrayList<Interval> ans = new ArrayList<Interval>();
        int len = intervals.size();
        if(len==0)return ans;
        for(int i = 1 ; i < len ; i++)
        {
                if(intervals.get(i).start <= intervals.get(i-1).end)
                {
                    intervals.get(i).start = Math.min(intervals.get(i-1).start,intervals.get(i).start);
                    intervals.get(i).end = Math.max(intervals.get(i-1).end,intervals.get(i).end);
                }
                else{
                        ans.add(intervals.get(i-1));
                }
        }
        ans.add(intervals.get(len-1));
        return ans;
    }
}

python

class Solution:
    def merge(self , intervals ):
        intervals.sort(key=lambda x:x.start)
        ans=[]
        if len(intervals) == 0:
            return ans
        for i in range(1,len(intervals)):
            if intervals[i].start<=intervals[i-1].end:
                intervals[i].start = min(intervals[i-1].start,intervals[i].start)
                intervals[i].end = max(intervals[i-1].end,intervals[i].end);
            else:
                ans.append(intervals[i-1])
        ans.append(intervals[len(intervals)-1])
        return ans