497. Random Point in Non-overlapping Rectangles Medium

1/**
2 * [497] Random Point in Non-overlapping Rectangles
3 *
4 * You are given an array of non-overlapping axis-aligned rectangles rects where rects[i] = [ai, bi, xi, yi] indicates that (ai, bi) is the bottom-left corner point of the i^th rectangle and (xi, yi) is the top-right corner point of the i^th rectangle. Design an algorithm to pick a random integer point inside the space covered by one of the given rectangles. A point on the perimeter of a rectangle is included in the space covered by the rectangle.
5 * Any integer point inside the space covered by one of the given rectangles should be equally likely to be returned.
6 * Note that an integer point is a point that has integer coordinates.
7 * Implement the Solution class:
8 * 
9 * 	Solution(int[][] rects) Initializes the object with the given rectangles rects.
10 * 	int[] pick() Returns a random integer point [u, v] inside the space covered by one of the given rectangles.
11 * 
12 *  
13 * Example 1:
14 * <img alt="" src="https://assets.leetcode.com/uploads/2021/07/24/lc-pickrandomrec.jpg" style="width: 419px; height: 539px;" />
15 * Input
16 * ["Solution", "pick", "pick", "pick", "pick", "pick"]
17 * [[[[-2, -2, 1, 1], [2, 2, 4, 6]]], [], [], [], [], []]
18 * Output
19 * [null, [1, -2], [1, -1], [-1, -2], [-2, -2], [0, 0]]
20 * Explanation
21 * Solution solution = new Solution([[-2, -2, 1, 1], [2, 2, 4, 6]]);
22 * solution.pick(); // return [1, -2]
23 * solution.pick(); // return [1, -1]
24 * solution.pick(); // return [-1, -2]
25 * solution.pick(); // return [-2, -2]
26 * solution.pick(); // return [0, 0]
27 * 
28 *  
29 * Constraints:
30 * 
31 * 	1 <= rects.length <= 100
32 * 	rects[i].length == 4
33 * 	-10^9 <= ai < xi <= 10^9
34 * 	-10^9 <= bi < yi <= 10^9
35 * 	xi - ai <= 2000
36 * 	yi - bi <= 2000
37 * 	All the rectangles do not overlap.
38 * 	At most 10^4 calls will be made to pick.
39 * 
40 */
41pub struct Solution {}
42
43// problem: https://leetcode.com/problems/random-point-in-non-overlapping-rectangles/
44// discuss: https://leetcode.com/problems/random-point-in-non-overlapping-rectangles/discuss/?currentPage=1&orderBy=most_votes&query=
45
46// submission codes start here
47
48struct Solution {
49        vec![]
50    }
51
52
53/** 
54 * `&self` means the method takes an immutable reference.
55 * If you need a mutable reference, change it to `&mut self` instead.
56 */
57impl Solution {
58
59    fn new(rects: Vec<Vec<i32>>) -> Self {
60        
61    }
62    
63    fn pick(&self) -> Vec<i32> {
64        
65    }
66}
67
68/**
69 * Your Solution object will be instantiated and called as such:
70 * let obj = Solution::new(rects);
71 * let ret_1: Vec<i32> = obj.pick();
72 */
73
74// submission codes end
75
76#[cfg(test)]
77mod tests {
78    use super::*;
79
80    #[test]
81    fn test_497() {
82    }
83}
84