1
class Solution {
2

3
  int[][] rects;
4
  TreeMap<Integer, Integer> weightedRectIndex = new TreeMap<>();
5
  int nPoints = 0;
6

7
  Random rng = new Random();
8

9
  public Solution(int[][] rects) {
10
    this.rects = rects;
11
    int index = 0;
12
    for (int[] rect : rects) {
13
      // inserts cumulative weight key pointing to rectangle index
14
      weightedRectIndex.put(nPoints, index++);
15
      nPoints += width(rect) * height(rect);
16
    }
17
  }
18

19
  public int[] pick() {
20
    // generates random point within total weight
21
    int point = rng.nextInt(nPoints);
22
    // finds appropriate rectangle
23
    var entry = weightedRectIndex.floorEntry(point);
24
    // find point within the current rectangle
25
    int rectPoint = point - entry.getKey();
26
    int[] rect = rects[entry.getValue()];
27
    return new int[] {rect[0] + rectPoint % width(rect), rect[1] + rectPoint / width(rect)};
28
  }
29

30
  private int width(int[] rect) {
31
    return rect[2] - rect[0] + 1;
32
  }
33

34
  private int height(int[] rect) {
35
    return rect[3] - rect[1] + 1;
36
  }
37
}