LeetCode 2020-11-18: Merge Intervals

Merge Intervals (medium) の挑戦メモ。

問題の概要

• 区間の配列が与えられるので、重複部分が存在する区間同士をすべて併合して重複部分の存在しない区間にする

考え方

• 区間の左端の昇順にソートしてから配列を先頭から走査すれば、マージ処理は簡単に実現できますね 🤗
  • 併合中の区間内に左端が存在する区間をすべて併合していく
    • 裏を返せば、併合中の区間内に左端が含まれない区間が見つかったところでいったん併合が終わり、その次の区間からまた併合が始まる、と
  • 時間計算量は O(n * log(n)) ですね
• 実装して submit → accept → Runtime 6ms で Your runtime beats 45.67 % of java submissions. は遅いですねえ… 🤔
  • Arrays.sort(Object[], Comparator) は結構オーバーヘッドが大きいので、別の方法を考えよう
• 例えば区間を int[] ではなく long で表してみたらどうか？
  • 上位 32 ビットで左端を、下位 32 ビットで右端を表す
  • これなら Arrays.sort(long[]) が使えてかなり早くなるはず
  • 実装 & submit → Runtime 2ms Your runtime beats 99.32 % of java submissions. まで早くできた
    • 最速は 0ms らしいが、到達できるのかな？
• 他には、マージソート的なアプローチもありえるかな？
  • ソートする際に区間のマージも行っちゃう的な
  • こちらも実装して submit → runtime 2ms だった

コード

int[][] を Arrays.sort() する方法

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) {
            return intervals;
        }

        Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));

        List<int[]> result = new ArrayList<>();
        int left = intervals[0][0], right = intervals[0][1];

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] > right) {
                result.add(new int[]{left, right});

                left = intervals[i][0];
                right = intervals[i][1];

            } else {
                right = Math.max(right, intervals[i][1]);
            }
        }

        result.add(new int[]{left, right});

        return result.toArray(new int[result.size()][]);
    }
}

Arrays.sort(long[]) でソートする方法

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) {
            return intervals;
        }

        long[] longs = new long[intervals.length];

        for (int i = 0; i < intervals.length; i++) {
            longs[i] = ((long) intervals[i][0] << 32) | intervals[i][1];
        }

        Arrays.sort(longs);

        long left = longs[0] >>> 32;
        long right = longs[0] & 0xffff_ffffL;
        int count = 0;

        for (int i = 1; i < longs.length; i++) {
            if ((longs[i] >>> 32) > right) {
                intervals[count][0] = (int) left;
                intervals[count][1] = (int) right;
                count++;

                left = longs[i] >>> 32;
                right = longs[i] & 0xffff_ffffL;

            } else {
                right = Math.max(right, longs[i] & 0xffff_ffffL);
            }
        }

        intervals[count][0] = (int) left;
        intervals[count][1] = (int) right;

        return Arrays.copyOf(intervals, count + 1);
    }
}

マージソート的なアプローチ

class Solution {
    private int[][] intervals;
    private int[][] work;

    public int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) {
            return intervals;
        }

        this.intervals = intervals;
        this.work = new int[intervals.length][2];

        int len = mergeRecursive(intervals, work, 0, intervals.length);
        return Arrays.copyOf(intervals, len);
    }

    int mergeRecursive(int[][] intervals, int[][] work, int beginIndex, int endIndex) {
        if (endIndex - beginIndex == 1) {
            this.work[beginIndex][0] = this.intervals[beginIndex][0];
            this.work[beginIndex][1] = this.intervals[beginIndex][1];
            return 1;
        }

        int mid = (beginIndex + endIndex) >>> 1;
        int leftLimit = mergeRecursive(work, intervals, beginIndex, mid) + beginIndex;
        int rightLimit = mergeRecursive(work, intervals, mid, endIndex) + mid;

        int writeIndex = beginIndex;
        int left = beginIndex;

        if (work[left][0] <= work[mid][0]) {
            intervals[writeIndex][0] = work[left][0];
            intervals[writeIndex][1] = work[left][1];
            left++;
        } else {
            intervals[writeIndex][0] = work[mid][0];
            intervals[writeIndex][1] = work[mid][1];
            mid++;
        }

        while (left < leftLimit && mid < rightLimit) {
            int[] small = work[left][0] <= work[mid][0]
                    ? work[left++] : work[mid++];
            if (small[0] <= intervals[writeIndex][1]) {
                intervals[writeIndex][1] = Math.max(intervals[writeIndex][1], small[1]);
            } else {
                writeIndex++;
                intervals[writeIndex][0] = small[0];
                intervals[writeIndex][1] = small[1];
            }
        }

        writeIndex = mergeRemains(intervals, work, leftLimit, writeIndex, left);
        writeIndex = mergeRemains(intervals, work, rightLimit, writeIndex, mid);

        return writeIndex + 1 - beginIndex;
    }

    int mergeRemains(int[][] intervals, int[][] work, int limit, int writeIndex, int index) {
        while (index < limit && work[index][0] <= intervals[writeIndex][1]) {
            intervals[writeIndex][1] = Math.max(intervals[writeIndex][1], work[index][1]);
            index++;
        }
        while (index < limit) {
            writeIndex++;
            intervals[writeIndex][0] = work[index][0];
            intervals[writeIndex][1] = work[index][1];
            index++;
        }
        return writeIndex;
    }
}