1
/**
2
 /**
3
 * @param {number[][]} rects
4
 */
5
var Solution = function (rects) {
6
  this.rects = rects;
7
  this.map = {};
8
  this.sum = 0;
9
  // we put in the map the number of points that belong to each rect
10
  for (let i in rects) {
11
    const rect = rects[i];
12
    // the number of points can be picked in this rectangle
13
    this.sum += (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
14
    this.map[this.sum] = i;
15
  }
16
  this.keys = Object.keys(this.map);
17
};
18

19
/**
20
 * @return {number[]}
21
 */
22
Solution.prototype.pick = function () {
23
  // random point pick between [1, this.sum]
24
  const randomPointPick = Math.floor(Math.random() * this.sum) + 1;
25

26
  // we look for the randomPointPick in the keys of the map
27
  let pointInMap;
28
  // the keys exists in map
29
  if (this.map[randomPointPick]) pointInMap = randomPointPick;
30
  // the key is the first in the map (we do this check before doing binary search because its out of boundery)
31
  else if (randomPointPick < this.keys[0]) pointInMap = this.keys[0];
32
  let high = this.keys.length;
33
  let low = 1;
34
  // binary search to find the closest key that bigger than randomPointPick
35
  while (low <= high && !pointInMap) {
36
    const mid = Math.floor(low + (high - low) / 2);
37
    if (
38
      randomPointPick > this.keys[mid - 1] &&
39
      randomPointPick < this.keys[mid]
40
    ) {
41
      pointInMap = this.keys[mid];
42
      break;
43
    } else if (randomPointPick > this.keys[mid]) {
44
      low = mid + 1;
45
    } else {
46
      high = mid - 1;
47
    }
48
  }
49

50
  // we have the point, now we can get which rect belong to that point
51
  const pointInRects = this.map[pointInMap];
52
  const chosen = this.rects[pointInRects];
53
  const rightX = chosen[2];
54
  const leftX = chosen[0];
55
  const topY = chosen[3];
56
  const bottomY = chosen[1];
57
  const pickX = Math.floor(Math.random() * (rightX - leftX + 1)) + leftX;
58
  const pickY = Math.floor(Math.random() * (topY - bottomY + 1)) + bottomY;
59
  return [pickX, pickY];
60
};
61

62
/**
63
 * Your Solution object will be instantiated and called as such:
64
 * var obj = new Solution(rects)
65
 * var param_1 = obj.pick()
66
 */