2250. Count Number of Rectangles Containing Each Point Medium

1/**
2 * [2250] Count Number of Rectangles Containing Each Point
3 *
4 * You are given a 2D integer array rectangles where rectangles[i] = [li, hi] indicates that i^th rectangle has a length of li and a height of hi. You are also given a 2D integer array points where points[j] = [xj, yj] is a point with coordinates (xj, yj).
5 * The i^th rectangle has its bottom-left corner point at the coordinates (0, 0) and its top-right corner point at (li, hi).
6 * Return an integer array count of length points.length where count[j] is the number of rectangles that contain the j^th point.
7 * The i^th rectangle contains the j^th point if 0 <= xj <= li and 0 <= yj <= hi. Note that points that lie on the edges of a rectangle are also considered to be contained by that rectangle.
8 *  
9 * Example 1:
10 * <img alt="" src="https://assets.leetcode.com/uploads/2022/03/02/example1.png" style="width: 300px; height: 509px;" />
11 * Input: rectangles = [[1,2],[2,3],[2,5]], points = [[2,1],[1,4]]
12 * Output: [2,1]
13 * Explanation:
14 * The first rectangle contains no points.
15 * The second rectangle contains only the point (2, 1).
16 * The third rectangle contains the points (2, 1) and (1, 4).
17 * The number of rectangles that contain the point (2, 1) is 2.
18 * The number of rectangles that contain the point (1, 4) is 1.
19 * Therefore, we return [2, 1].
20 *
21 * Example 2:
22 * <img alt="" src="https://assets.leetcode.com/uploads/2022/03/02/example2.png" style="width: 300px; height: 312px;" />
23 * Input: rectangles = [[1,1],[2,2],[3,3]], points = [[1,3],[1,1]]
24 * Output: [1,3]
25 * Explanation:
26 * The first rectangle contains only the point (1, 1).
27 * The second rectangle contains only the point (1, 1).
28 * The third rectangle contains the points (1, 3) and (1, 1).
29 * The number of rectangles that contain the point (1, 3) is 1.
30 * The number of rectangles that contain the point (1, 1) is 3.
31 * Therefore, we return [1, 3].
32 *
33 *  
34 * Constraints:
35 *
36 * 1 <= rectangles.length, points.length <= 5 * 10^4
37 * rectangles[i].length == points[j].length == 2
38 * 1 <= li, xj <= 10^9
39 * 1 <= hi, yj <= 100
40 * All the rectangles are unique.
41 * All the points are unique.
42 *
43 */
44pub struct Solution {}
45
46// problem: https://leetcode.com/problems/count-number-of-rectangles-containing-each-point/
47// discuss: https://leetcode.com/problems/count-number-of-rectangles-containing-each-point/discuss/?currentPage=1&orderBy=most_votes&query=
48
49// submission codes start here
50
51impl Solution {
52    pub fn count_rectangles(rectangles: Vec<Vec<i32>>, points: Vec<Vec<i32>>) -> Vec<i32> {
53        let mut data: Vec<Vec<i32>> = vec![vec![]; 101];
54
55        for r in rectangles {
56            data[r[1] as usize].push(r[0]);
57        }
58
59        for d in &mut data {
60            d.sort();
61        }
62
63        let mut result = vec![0_i32; points.len()];
64        for (i, p) in points.iter().enumerate() {
65            for j in p[1]..101 {
66                if data[j as usize].is_empty() {
67                    continue;
68                }
69                match data[j as usize].binary_search(&p[0]) {
70                    Ok(x) => result[i] += (data[j as usize].len() - x) as i32,
71                    Err(y) => result[i] += (data[j as usize].len() - y) as i32,
72                }
73            }
74        }
75
76        result
77    }
78}
79
80// submission codes end
81
82#[cfg(test)]
83mod tests {
84    use super::*;
85
86    #[test]
87    fn test_2250_1() {
88        assert_eq!(Solution::count_rectangles(vec![vec![1, 1], vec![2, 2], vec![3, 3]], vec![vec![1, 3], vec![1, 1]]), vec![1, 3]);
89    }
90}
91