3111. Minimum Rectangles to Cover Points Medium

1/**
2 * [3111] Minimum Rectangles to Cover Points
3 *
4 * You are given a 2D integer array points, where points[i] = [xi, yi]. You are also given an integer w. Your task is to cover all the given points with rectangles.
5 * Each rectangle has its lower end at some point (x1, 0) and its upper end at some point (x2, y2), where x1 <= x2, y2 >= 0, and the condition x2 - x1 <= w must be satisfied for each rectangle.
6 * A point is considered covered by a rectangle if it lies within or on the boundary of the rectangle.
7 * Return an integer denoting the minimum number of rectangles needed so that each point is covered by at least one rectangle.
8 * Note: A point may be covered by more than one rectangle.
9 *  
10 * <strong class="example">Example 1:
11 * <img alt="" src="https://assets.leetcode.com/uploads/2024/03/04/screenshot-from-2024-03-04-20-33-05.png" style="width: 205px; height: 300px;" />
12 * <div class="example-block" style="
13 *     border-color: var(--border-tertiary);
14 *     border-left-width: 2px;
15 *     color: var(--text-secondary);
16 *     font-size: .875rem;
17 *     margin-bottom: 1rem;
18 *     margin-top: 1rem;
19 *     overflow: visible;
20 *     padding-left: 1rem;
21 * ">
22 * Input: <span class="example-io" style="
23 *     font-family: Menlo,sans-serif;
24 *     font-size: 0.85rem;
25 * ">points = [[2,1],[1,0],[1,4],[1,8],[3,5],[4,6]], w = 1</span>
26 * Output: <span class="example-io" style="
27 *     font-family: Menlo,sans-serif;
28 *     font-size: 0.85rem;
29 * ">2</span>
30 * Explanation: 
31 * The image above shows one possible placement of rectangles to cover the points:
32 * 
33 * 	A rectangle with a lower end at (1, 0) and its upper end at (2, 8)
34 * 	A rectangle with a lower end at (3, 0) and its upper end at (4, 8)
35 * </div>
36 * <strong class="example">Example 2:
37 * <img alt="" src="https://assets.leetcode.com/uploads/2024/03/04/screenshot-from-2024-03-04-18-59-12.png" style="width: 260px; height: 250px;" />
38 * <div class="example-block" style="
39 *     border-color: var(--border-tertiary);
40 *     border-left-width: 2px;
41 *     color: var(--text-secondary);
42 *     font-size: .875rem;
43 *     margin-bottom: 1rem;
44 *     margin-top: 1rem;
45 *     overflow: visible;
46 *     padding-left: 1rem;
47 * ">
48 * Input: <span class="example-io" style="
49 *     font-family: Menlo,sans-serif;
50 *     font-size: 0.85rem;
51 * ">points = [[0,0],[1,1],[2,2],[3,3],[4,4],[5,5],[6,6]], w = 2</span>
52 * Output: <span class="example-io" style="
53 *     font-family: Menlo,sans-serif;
54 *     font-size: 0.85rem;
55 * ">3</span>
56 * Explanation: 
57 * The image above shows one possible placement of rectangles to cover the points:
58 * 
59 * 	A rectangle with a lower end at (0, 0) and its upper end at (2, 2)
60 * 	A rectangle with a lower end at (3, 0) and its upper end at (5, 5)
61 * 	A rectangle with a lower end at (6, 0) and its upper end at (6, 6)
62 * </div>
63 * <strong class="example">Example 3:
64 * <img alt="" src="https://assets.leetcode.com/uploads/2024/03/04/screenshot-from-2024-03-04-20-24-03.png" style="height: 150px; width: 127px;" />
65 * <div class="example-block" style="
66 *     border-color: var(--border-tertiary);
67 *     border-left-width: 2px;
68 *     color: var(--text-secondary);
69 *     font-size: .875rem;
70 *     margin-bottom: 1rem;
71 *     margin-top: 1rem;
72 *     overflow: visible;
73 *     padding-left: 1rem;
74 * ">
75 * Input: <span class="example-io" style="
76 *     font-family: Menlo,sans-serif;
77 *     font-size: 0.85rem;
78 * ">points = [[2,3],[1,2]], w = 0</span>
79 * Output: <span class="example-io" style="
80 *     font-family: Menlo,sans-serif;
81 *     font-size: 0.85rem;
82 * ">2</span>
83 * Explanation: 
84 * The image above shows one possible placement of rectangles to cover the points:
85 * 
86 * 	A rectangle with a lower end at (1, 0) and its upper end at (1, 2)
87 * 	A rectangle with a lower end at (2, 0) and its upper end at (2, 3)
88 * </div>
89 *  
90 * Constraints:
91 * 
92 * 	1 <= points.length <= 10^5
93 * 	points[i].length == 2
94 * 	0 <= xi == points[i][0] <= 10^9
95 * 	0 <= yi == points[i][1] <= 10^9
96 * 	0 <= w <= 10^9
97 * 	All pairs (xi, yi) are distinct.
98 * 
99 */
100pub struct Solution {}
101
102// problem: https://leetcode.com/problems/minimum-rectangles-to-cover-points/
103// discuss: https://leetcode.com/problems/minimum-rectangles-to-cover-points/discuss/?currentPage=1&orderBy=most_votes&query=
104
105// submission codes start here
106
107impl Solution {
108    pub fn min_rectangles_to_cover_points(points: Vec<Vec<i32>>, w: i32) -> i32 {
109        0
110    }
111}
112
113// submission codes end
114
115#[cfg(test)]
116mod tests {
117    use super::*;
118
119    #[test]
120    fn test_3111() {
121    }
122}
123