56. 合并区间

方法一：排序+遍历

class Solution {
    public int[][] merge(int[][] intervals) {
        int n = intervals.length;
        //按照区间的左侧位置排列数组
        Arrays.sort(intervals, (v1, v2) -> (v1[0] - v2[0]));
        int[][] res = new int[n][2];
        int idx = -1;
        //遍历数组
        for (int[] interval : intervals) {
            // 如果结果数组是空的，或者当前区间的起始位置 > 结果数组中最后区间的终止位置
            // 则不合并，直接将当前区间加入结果数组。
            if (idx == -1 || res[idx][1] < interval[0]) {
                res[++idx] = interval;
            } else {
                //反之，将区间合并入之前加入的区间
                res[idx][1] = Math.max(res[idx][1], interval[1]);
            }
        }
        return Arrays.copyOf(res, idx + 1);
    }
}

方法二：位图 bitSet

• 位图实现了一种直观的想法：开一个大数组，遍历所有区间，每个区间的每一个数对应的大数组索引位置++，数组中不为零的区间段，即为合并之后的答案。

class Solution {
    public int[][] merge(int[][] intervals) {
        BitSet bitSet = new BitSet();
        int max = 0;
        for (int[] interval : intervals) {
            //[1,4]&[5,6]在数轴上是不连续的，但是BitSet上却是连续的，
            //所以进行乘2，使他们从BitSet上看也不是连续的
            int temp = interval[1] * 2 + 1;
            //BitSet 的set方法，将[left, right) 区间置为true/false
            bitSet.set(interval[0] * 2, temp, true);
            //找出最大值，方便之后遍历
            max = temp >= max ? temp : max;
        }

        int index = 0, count = 0;
        while (index < max) {
            //nextSetBit(index)：找出从index开始，第一个为true的索引
            int start = bitSet.nextSetBit(index);
            //nextClearBit(start)：找出从start开始，第一个为false的索引
            int end = bitSet.nextClearBit(start);
            //映射到原区间
            int[] item = {start / 2, (end - 1) / 2};
            //count表示最终的区间数目，同时也充当了索引
            intervals[count++] = item;
            //index指向end，继续遍历
            index = end;
        }
        int[][] ret = new int[count][2];
        for (int i = 0; i < count; i++) {
            ret[i] = intervals[i];
        }

        return ret;
    }
}

BitSet类常用方法