题解 | #合并区间#

小数据O(nlgn)， 大数据O(n)， 空间复杂度不保证，不过感觉也没那么大吧！


import java.util.*;

/*
 * public class Interval {
 *   int start;
 *   int end;
 *   public Interval(int start, int end) {
 *     this.start = start;
 *     this.end = end;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param intervals Interval类ArrayList 
     * @return Interval类ArrayList
     */
    public ArrayList<Interval> merge (ArrayList<Interval> intervals) {
        int n = intervals.size();
        if (n < 2) {
            return intervals;
        }
        ArrayList<Interval> intervalAux = new ArrayList<>(intervals);
        if (n < 10000) {
            mergeSort(intervals, intervalAux, 0, intervals.size() - 1);
        } else {
            intervals = radixSort(intervals);
        }
        ArrayList<Interval> retList = new ArrayList<>();
        Interval tmp;
        for (Interval interval : intervals) {
            if (!retList.isEmpty() && retList.get(retList.size() - 1).end >= interval.start) {
                tmp = retList.remove(retList.size() - 1);
                tmp.end = Math.max(interval.end, tmp.end);
                retList.add(tmp);
            } else {
                retList.add(interval);
            }
        }
        return retList;
    }

    private ArrayList<Interval> radixSort(ArrayList<Interval> intervals) {
        int max = 0;
        for (Interval interval : intervals) {
            if (max < interval.start) {
                max = interval.start;
            }
        }
        Interval[] intervalArray = new Interval[max + 1];
        for (Interval interval : intervals) {
            if (intervalArray[interval.start] == null) {
                intervalArray[interval.start] = interval;
            } else {
                intervalArray[interval.start].end =
                        Math.max(intervalArray[interval.start].end, interval.end);
            }
        }
        ArrayList<Interval> intervalList = new ArrayList<>();
        for (int i = 0; i <= max; i++) {
            if (intervalArray[i] != null) {
                intervalList.add(intervalArray[i]);
            }
        }
        return intervalList;
    }

    private void mergeSort(ArrayList<Interval> intervals, ArrayList<Interval> intervalAux, int lo, int hi) {
        if (lo + 15 >= hi) {
            insertSort(intervals, lo, hi);
            return;
        }
        int mid = lo + (hi - lo) / 2;
        mergeSort(intervalAux, intervals, lo, mid);
        mergeSort(intervalAux, intervals, mid + 1, hi);
        int left = lo, right = mid + 1;
        for (int i = lo; i <= hi; i++) {
            intervals.remove(i);
            if (left > mid) {
                intervals.add(i, intervalAux.get(right++));
            } else if (right > hi) {
                intervals.add(i, intervalAux.get(left++));
            } else if (intervalAux.get(left).start <= intervalAux.get(right).start) {
                intervals.add(i, intervalAux.get(left++));
            } else {
                intervals.add(i, intervalAux.get(right++));
            }
        }
    }

    private void insertSort(ArrayList<Interval> intervals, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        Interval tmp, tmp1;
        for (int i = lo + 1; i <= hi; i++) {
            if (intervals.get(i).start < intervals.get(i - 1).start) {
                tmp = intervals.get(i);
                int j = i;
                while (j > lo && tmp.start < intervals.get(j - 1).start) {
                    tmp1 = intervals.get(j - 1);
                    intervals.remove(j);
                    intervals.add(j, tmp1);
                    j--;
                }
                intervals.remove(j);
                intervals.add(j, tmp);
            }
        }
    }
}