3394. Check if Grid can be Cut into Sections Medium

1/**
2 * [3394] Check if Grid can be Cut into Sections
3 *
4 * You are given an integer n representing the dimensions of an n x n<!-- notionvc: fa9fe4ed-dff8-4410-8196-346f2d430795 --> grid, with the origin at the bottom-left corner of the grid. You are also given a 2D array of coordinates rectangles, where rectangles[i] is in the form [startx, starty, endx, endy], representing a rectangle on the grid. Each rectangle is defined as follows:
5 * 
6 * 	(startx, starty): The bottom-left corner of the rectangle.
7 * 	(endx, endy): The top-right corner of the rectangle.
8 * 
9 * Note that the rectangles do not overlap. Your task is to determine if it is possible to make either two horizontal or two vertical cuts on the grid such that:
10 * 
11 * 	Each of the three resulting sections formed by the cuts contains at least one rectangle.
12 * 	Every rectangle belongs to exactly one section.
13 * 
14 * Return true if such cuts can be made; otherwise, return false.
15 *  
16 * <strong class="example">Example 1:
17 * <div class="example-block">
18 * Input: <span class="example-io">n = 5, rectangles = [[1,0,5,2],[0,2,2,4],[3,2,5,3],[0,4,4,5]]</span>
19 * Output: <span class="example-io">true</span>
20 * Explanation:
21 * <img alt="" src="https://assets.leetcode.com/uploads/2024/10/23/tt1drawio.png" style="width: 285px; height: 280px;" />
22 * The grid is shown in the diagram. We can make horizontal cuts at y = 2 and y = 4. Hence, output is true.
23 * </div>
24 * <strong class="example">Example 2:
25 * <div class="example-block">
26 * Input: <span class="example-io">n = 4, rectangles = [[0,0,1,1],[2,0,3,4],[0,2,2,3],[3,0,4,3]]</span>
27 * Output: <span class="example-io">true</span>
28 * Explanation:
29 * <img alt="" src="https://assets.leetcode.com/uploads/2024/10/23/tc2drawio.png" style="width: 240px; height: 240px;" />
30 * We can make vertical cuts at x = 2 and x = 3. Hence, output is true.
31 * </div>
32 * <strong class="example">Example 3:
33 * <div class="example-block">
34 * Input: <span class="example-io">n = 4, rectangles = [[0,2,2,4],[1,0,3,2],[2,2,3,4],[3,0,4,2],[3,2,4,4]]</span>
35 * Output: <span class="example-io">false</span>
36 * Explanation:
37 * We cannot make two horizontal or two vertical cuts that satisfy the conditions. Hence, output is false.
38 * </div>
39 *  
40 * Constraints:
41 * 
42 * 	3 <= n <= 10^9
43 * 	3 <= rectangles.length <= 10^5
44 * 	0 <= rectangles[i][0] < rectangles[i][2] <= n
45 * 	0 <= rectangles[i][1] < rectangles[i][3] <= n
46 * 	No two rectangles overlap.
47 * 
48 */
49pub struct Solution {}
50
51// problem: https://leetcode.com/problems/check-if-grid-can-be-cut-into-sections/
52// discuss: https://leetcode.com/problems/check-if-grid-can-be-cut-into-sections/discuss/?currentPage=1&orderBy=most_votes&query=
53
54// submission codes start here
55
56impl Solution {
57    pub fn check_valid_cuts(n: i32, rectangles: Vec<Vec<i32>>) -> bool {
58        false
59    }
60}
61
62// submission codes end
63
64#[cfg(test)]
65mod tests {
66    use super::*;
67
68    #[test]
69    fn test_3394() {
70    }
71}
72