Java TreeMap
\nclass Solution {\n    TreeMap<Integer, Integer> map;\n    int[][] rs;\n    int sum = 0;\n    Random rand = new Random();\n    public Solution(int[][] rects) {
```\nclass Solution {\n    TreeMap<Integer, Integer> map;\n    int[][] rs;\n    int sum = 0;\n    Random rand = new Random();\n    public Solution(int[][] rects) {\n        map = new TreeMap<>();\n        rs = rects;\n        for (int i = 0; i < rs.length; i++) {\n            map.put(sum, i);\n            sum += (rs[i][2] - rs[i][0] + 1) * (rs[i][3] - rs[i][1] + 1);\n        }\n    }\n    \n    public int[] pick() {\n        int rd = rand.nextInt(sum), k = map.floorKey(rd), r[] = rs[map.get(k)], diff = rd - k, w = r[2] - r[0] + 1;\n        return new int[]{r[0] + diff % w, r[1] + diff / w};\n    }\n}\n```
[]