← 返回 bytedance 的题目列表Random Point in Non-overlapping Rectangles
类型：online_judge
Design a randomized algorithm to generate a random point in a group of non-overlapping rectangles. The area of each rectangle represents the probability of generating the point.
Given a non-overlapping list of rectangles represented as [x1, y1, x2, y2]. Implement a class Solution like below:
Solution(int[][] rects) Initializing object using a 2D array of integers rects, where rects[i] represents the i-th non-overlapping rectangle.
int[] pick() Return a [x, y] point representing a random selection.
Example 1:
Input:
["Solution", "pick", "pick", "pick", "pick", "pick"]
[[[1, 1, 5, 5]], [], [], [], [], []]
Output:
[null, [4, 1], [4, 1], [3, 3], [2, 4], [3, 2]]
Explanation:
Solution solution = new Solution([[1, 1, 5, 5]]);
solution.pick(); // Generates (4,1)
solution.pick(); // Generates (4,1)
solution.pick(); // Generates (3,3)
solution.pick(); // Generates (2,4)
solution.pick(); // Generates (3,2)
Note:
1 <= rects.length <= 100
rects[i].length == 4
-10^9 <= rects[i][j] <= 10^9
Rectangle width and height must be greater than 0
pick can be called up to 10^4 times
Example
Input
[[1, 1, 5, 5]]
pick()
pick()
pick()
pick()
pick()
Output
[null, [4, 4], [1, 2], [2, 3], [5, 5], [1, 1]]