Design a class Solution over a list of non-overlapping axis-aligned rectangles [x1, y1, x2, y2], where (x1, y1) is the bottom-left corner and (x2, y2) the top-right one, both included.
new Solution(rects, rng) prepares the picker. rng returns numbers in [0, 1)pick() returns a point [x, y] with integer coordinates that lies in some rectangle (edges and corners count). Every integer point of the union must be equally likely- A rectangle holds
(x2 - x1 + 1) * (y2 - y1 + 1) integer points, so choosing a rectangle first with equal probability would be wrong - Target: setup O(n), pick O(log n)
- Draw exactly once per pick:
r = Math.floor(rng() * total), where total is the number of integer points in all rectangles, numbers every point of the union, so tests can script the generator