Medium
Quiz
#497 Random Point in Non-overlapping Rectangles
APPROACH
Design a data structure that picks a uniformly random integer lattice point from the union of non-overlapping axis-aligned rectangles. Each rectangle is given as [ai, bi, xi, yi] where (ai, bi) is the bottom-left corner and (xi, yi) is the top-right corner. Points on the perimeter count as inside.
Implement the Solution class:
- Solution(int[][] rects) — initializes the object with the rectangle list.
- int[] pick() — returns a uniformly random integer point [u, v] across all rectangles.
Example 1:
Input
["Solution", "pick", "pick", "pick", "pick", "pick"]
[[[[-2, -2, 1, 1], [2, 2, 4, 6]]], [], [], [], [], []]
Output
[null, [1, -2], [1, -1], [-1, -2], [-2, -2], [0, 0]]
Example 2:
Explanation
Solution solution = new Solution([[-2, -2, 1, 1], [2, 2, 4, 6]]);
solution.pick(); // return [1, -2]
solution.pick(); // return [1, -1]
solution.pick(); // return [-1, -2]
solution.pick(); // return [-2, -2]
solution.pick(); // return [0, 0]
1 of 4
1:00
What is the optimal approach for this problem?