leetCode：497. Random Point in Non-overlapping Rectangles

leetCodeの「497. Random Point in Non-overlapping Rectangles」を解いた。
https://leetcode.com/problems/random-point-in-non-overlapping-rectangles/

初めて Map#ceilingKey() を使ったので、今後の参考のため、解答コードをここに残しておく。

import java.util.Random;
import java.util.TreeMap;

class Solution {
    TreeMap<Integer, Integer> areaToRect = new TreeMap<>();
    int[][] rects;
    int area;
    Random random = new Random();

    public Solution(int[][] rects) {
        this.rects = rects;
        for(int i = 0; i < rects.length; i++) {
            int[] rect = rects[i];
            area += (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
            areaToRect.put(area, i);
        }
    }

    public int[] pick() {
        // Map#ceilingKey() は、メソッド名の通り、「天井」となる key 値を返す。
        // 例えば、Map に格納済みの key 値が 1, 3, 6, 10 だったとしたら、
        // input -> output は以下のようになる。
        // ceilingKey(3) -> 3
        // ceilingKey(4) -> 6
        // ceilingKey(5) -> 6
        // ceilingKey(6) -> 6
        // ceilingKey(7) -> 10
        int pickUpedArea = areaToRect.ceilingKey(random.nextInt(area + 1));
        int[] rect = rects[areaToRect.get(pickUpedArea)];
        int left = rect[0], right = rect[2], bottom = rect[1], top = rect[3];
        int x = left + random.nextInt(right - left + 1);
        int y = bottom + random.nextInt(top - bottom + 1);
        return new int[]{x, y};
    }
}