LeetCoding Challenge Oct. 4: Remove Covered Intervals

LeetCode October Challenge の 4 日目。

今日の問題は Remove Covered Intervals。

問題の概要

• int[][] の型で与えられる区間の配列より、配列上の他の区間によって完全に包まれる区間を除去した後の 区間の個数 を求める

実装の手順・考え方

• この手の問題に適したデータ構造があるのかどうかがよくわらかない… あるのかな？
• ひとまず区間の左端の昇順にソートしておこう

ヒープを用いた実装

• 区間がとりうる最小値 (0) から最大値 (10^5) までをループで回そう (ループ変数: index)
• ヒープ (PriorityQueue クラス) を 2 つ使おう
  • ある地点 index を含む区間の左端を保持する leftIndexes
  • ある地点 index を含む区間を右端の昇順に並べた activeIntervals
• index をいい感じに更新しつつ、その index を含む新たな区間を見つけたら leftIndexes と activeIntervals に add する
• index が activeIntervals の先頭の区間の右端に達したときに、その区間の左端が leftIndexes の先頭の値以上だったら他の区間に含まれていることを表すので、 削除回数 をインクリメントする
• すべての区間を処理し終えたところで、intervals.length - 削除回数 を戻り値とする
• この実装を submit したら runtime 28ms / Your runtime beats 7.11 % of java submissions. と、とても残念な成績に終わってしまった 😭
  • 時間計算量的にはソートが O(n * log(n))、ヒープ操作が 1 回あたり O(log(n)) なので、全体としては O(n * log(n)) になるのだが…

わりとナイーブな実装

• PriorityQueue を使うとオーバーヘッドが大きそうなので、余計なデータ構造を使わないナイーブな実装にしてみよう
• 区間をその左端の昇順にソートしておくのは同じとして、同じ左端を持つ区間は右端がより遠いところにある区間を先に並べるようにしよう

Arrays.sort(intervals, (a, b) -> {
    int r = Integer.compare(a[0], b[0]);
    return r != 0 ? r : -Integer.compare(a[1], b[1]);
});

• 区間の配列を先頭から順に走査して、i 番目の区間が包含する区間が存在するかどうかを i + 1 番目以降の区間に対してチェックしよう
  • i + j 番目の区間の左端が i 番目の区間の右端に達したら、i をインクリメントする
  • 随分とナイーブなアルゴリズムであり、計算量は O(n^2) になるはず
• この実装は 14ms とヒープを用いた方法よりは速いものの、Your runtime beats 12.44 % of java submissions. とまだまだ上位には及ばない結果に… 😭😭😭

考察

上位陣の実装をサンプリングして見つつ、どうすべきだったかを考える。

• ナイーブな実装のやつ、走査部分に最適化の余地が残ってたよ… 🤦‍♂️
  • 区間の配列が左端の昇順に並んでいることをちゃんと利用すれば O(n) の時間計算量に抑えられるはずだった 🙈
  • 最適化を施して submit すると runtime 4~5ms となり、これは runtime の最頻値に相当する
  • コードはこちら
• Runtime 3ms 以下のやつを見ると、もはやソートなしの最も素朴な二重ループによる実装だったりして 🤔 な顔になってしまう

コード

ヒープを用いた実装

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

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

        PriorityQueue<Integer> leftIndexes = new PriorityQueue<>();
        PriorityQueue<int[]> activeIntervals = new PriorityQueue<>((a, b) -> {
            int r = Integer.compare(a[1], b[1]);
            if (r != 0) {
                return r;
            }
            return -Integer.compare(a[0], b[0]);
        });

        int removedCount = 0;
        int index = 0;
        int intervalsIndex = 0;
        while (intervalsIndex < intervals.length || !activeIntervals.isEmpty()) {
            index = Math.min(
                    !activeIntervals.isEmpty() ? activeIntervals.peek()[1] : Integer.MAX_VALUE,
                    intervalsIndex < intervals.length ? intervals[intervalsIndex][0] : Integer.MAX_VALUE);

            while (intervalsIndex < intervals.length && intervals[intervalsIndex][0] <= index) {
                leftIndexes.add(intervals[intervalsIndex][0]);
                activeIntervals.add(intervals[intervalsIndex]);
                intervalsIndex++;
            }

            while (!activeIntervals.isEmpty() && activeIntervals.peek()[1] <= index) {
                int[] interval = activeIntervals.poll();
                leftIndexes.remove(interval[0]);
                if (!leftIndexes.isEmpty() && interval[0] >= leftIndexes.peek()) {
                    removedCount++;
                }
            }
        }

        return intervals.length - removedCount;
    }
}

わりとナイーブな実装

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

        Arrays.sort(intervals, (a, b) -> {
            int r = Integer.compare(a[0], b[0]);
            return r != 0 ? r : -Integer.compare(a[1], b[1]);
        });

        int left = 0, right = 1;
        int removedCount = 0;
        while (left < intervals.length) {
            if (right == intervals.length
                    || intervals[right][0] >= intervals[left][1]) {
                left++;
                right = left + 1;
                continue;
            }

            if (intervals[right][0] >= 0
                    && intervals[right][1] <= intervals[left][1]) {
                intervals[right][0] = -1;
                removedCount++;
            }

            right++;
        }

        return intervals.length - removedCount;
    }
}

上位陣のコードを見ながら最適化した結果

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

        Arrays.sort(intervals, (a, b) -> {
            int r = Integer.compare(a[0], b[0]);
            return r != 0 ? r : -Integer.compare(a[1], b[1]);
        });

        int maxRight = intervals[0][1];
        int removedCount = 0;

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][1] <= maxRight) {
                removedCount++;
            } else {
                maxRight = intervals[i][1];
            }
        }

        return intervals.length - removedCount;
    }
}