题解 | #合并区间#

看到大部分题解都是sort排序，然后遍历合并，我分享一种比较取巧的合并。

因为数值范围较小，所以先开 200001 的数组 lengthArray ，里面保存的是从改位置开始，共有几个数字，例如 [10, 20] 就可以转换为 lengthArray[10] = 11，标识从坐标 10 开始有 11 个数字（包括自身）。随后遍历 lengthArray，如果存在 length，则length--；如果 length变为 0，说明一个范围终止，则加入结果队列中。

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) {
        // write code here
        if (intervals.size() <= 1) {
            return intervals;
        }
        int maxLength = 200001;
        int[] lengthArray = new int[maxLength];
        for (Interval interval : intervals) {
            lengthArray[interval.start] = Math.max(interval.end - interval.start + 1, lengthArray[interval.start]);
        }
        int startPos = -1;
        int length = -1;
        ArrayList<Interval> resultList = new ArrayList<>();
        for (int i = 0; i < maxLength; i++) {
            if (length > 0) {
                length--;
                if (length == 0) {
                    resultList.add(new Interval(startPos, i - 1));
                    length = -1;
                    startPos = -1;
                }
            }
            if (length > 0 && lengthArray[i] > 0) {
                length = Math.max(length, lengthArray[i]);
            } else if (length == -1 && lengthArray[i] > 0) {
                startPos = i;
                length = lengthArray[i];
            }
        }
        return resultList;
    }
}