LeetCoding Challenge Oct. 10: Min # of Arrows to Burst...

LeetCode October Challenge の 10 日目。

今日の問題は Minimum Number of Arrows to Burst Balloons。

(zenn.dev はタイトルに設定できる文字数に上限があるようで、今日の問題はタイトルすべてを記述できない 😢)

問題の概要

• xy 平面上にいくつかの風船が配置されている
• 一つの風船は、その大きさが「x 座標における左端の位置と右端の位置」の組で表される
• y 軸と平行に矢を射って風船を割る場合に、すべての風船を割るのに必要な最小本数はいくつか？
  • 矢は無限に飛んでいくものとする

考え方

• ぱっと見すると、つい最近解いた Remove Covered Intervals と同じ要領で解けるんじゃないかね 🤔
  • 風船の左端の位置の昇順に並べて、ループを回す
  • ループするたびに、「右端の位置の最小値」を更新していく
  • いまループで処理している風船の左端が「右端の位置の最小値」を超えたら、必要な矢の本数をインクリメントする
    • 「右端の位置の最小値」は、その風船の右端で書き換える
• 果たしてこれで本当に 矢の最小本数 を求めることができるのかが不安ではあるが…
• ひとまず実装してみて submit → accept 🤗
  • Weekly のコンテスト中に submit したせいか、runtime が submit ごとに 20~30ms ぐらいでばらついて結果が安定しない…
  • 13 時過ぎてから submit して 16ms ぐらいにはなったが、まだ落ち着いていないのかな？
    • 16 ms は最頻値の右隣で Your runtime beats 56.09 % of java submissions.

コード

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points == null) {
            return 0;
        }
        if (points.length <= 1) {
            return points.length;
        }

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

        int result = 1;
        int right = points[0][1];
        for (int i = 1; i < points.length; i++) {
            int[] point = points[i];
            if (point[0] > right) {
                result++;
                right = point[1];
            } else {
                right = Math.min(right, point[1]);
            }
        }

        return result;
    }
}