## Random Point in Non-overlapping Rectangles

• Time:Constructor: O(n), pick(): O(\log n);
• Space:O(n)

## C++

``````class Solution {
public:
Solution(vector<vector<int>>& rects) : rects(move(rects)) {
for (const auto& r : this->rects)
areas.push_back(getArea(r));
partial_sum(begin(areas), end(areas), begin(areas));
}

vector<int> pick() {
const int target = rand() % areas.back();
const int index =
upper_bound(begin(areas), end(areas), target) - begin(areas);
const auto& r = rects[index];
return {rand() % (r[2] - r[0] + 1) + r[0],
rand() % (r[3] - r[1] + 1) + r[1]};
}

private:
const vector<vector<int>> rects;
vector<int> areas;

int getArea(const vector<int>& r) {
return (r[2] - r[0] + 1) * (r[3] - r[1] + 1);
}
};
``````

## JAVA

``````class Solution {
public Solution(int[][] rects) {
this.rects = rects;
areas = new int[rects.length];
for (int i = 0; i < rects.length; ++i)
areas[i] = getArea(rects[i]) + (i > 0 ? areas[i - 1] : 0);
}

public int[] pick() {
final int target = rand.nextInt(areas[areas.length - 1]);
final int index = firstGreater(areas, target);
final int[] r = rects[index];
return new int[] {
rand.nextInt(r[2] - r[0] + 1) + r[0],
rand.nextInt(r[3] - r[1] + 1) + r[1],
};
}

private int[][] rects;
private int[] areas;
private Random rand = new Random();

private int getArea(int[] r) {
return (r[2] - r[0] + 1) * (r[3] - r[1] + 1);
}

private int firstGreater(int[] areas, int target) {
int l = 0;
int r = areas.length;
while (l < r) {
final int m = (l + r) / 2;
if (areas[m] > target)
r = m;
else
l = m + 1;
}
return l;
}
}
``````

## Python

``````class Solution:
def __init__(self, rects: List[List[int]]):
self.rects = rects
self.areas = list(accumulate(
[(x2 - x1 + 1) * (y2 - y1 + 1) for x1, y1, x2, y2 in rects]))

def pick(self) -> List[int]:
index = bisect_right(self.areas, randint(0, self.areas[-1] - 1))
x1, y1, x2, y2 = self.rects[index]
return [randint(x1, x2), randint(y1, y2)]
``````