题解 | #合并区间#

快排+一次遍历，时间复杂度nlogn+n
关键点：两个区间能合并的条件，如已排序的两区间[a,b]，[c,d]，能合并的条件为b>c且d>a，合并后的区间左区间为a，c中的较小值，右区间为b,d中较大值
代码如下：

import java.util.*;
/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */


public class Solution {
    void qsort(ArrayList<Interval> in,int s,int e){  //递归快排函数
        if(s>=e)return;
        int i=s,j=e;
        Interval tmp=in.get(s);
        while(i<j){
            while(in.get(j).start>=tmp.start &&i<j) j--;
            in.set(i,in.get(j));
            while(in.get(i).start<=tmp.start &&i<j) i++;
            in.set(j,in.get(i));
        }
        in.set(i,tmp);
        qsort(in,s,i-1);
        qsort(in,i+1,e);
     }
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        if(intervals.size()<=1) return intervals;
        ArrayList<Interval> res=new ArrayList<>();
        qsort(intervals,0,intervals.size()-1);
        for(int i=0;i<intervals.size()-1;i++){
            if(intervals.get(i).end>=intervals.get(i+1).start 
               &&intervals.get(i+1).end >=intervals.get(i).start){
                Interval in=new Interval(
                    Math.min(intervals.get(i).start,intervals.get(i+1).start),   //左区间取较小值
                    Math.max(intervals.get(i).end,intervals.get(i+1).end)    //右区间去较大值
                );
                intervals.set(i,in);
                intervals.remove(i+1); //合并后移除后一项
                i--;  //下标指向合并后的位置
            }
        }
         return intervals;
    }
}