diff options
author | Jack Sangdahl <[email protected]> | 2025-03-24 19:08:46 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-03-24 19:08:46 -0600 |
commit | 88adbcc57a22112c6e45c61d3b1b77f315066b87 (patch) | |
tree | 50016bab652c76707640736a8dcfb0bb5420e6e0 /check_grid_cut_section.py | |
parent | dff62d9aba66fa4d79315d74c60558b12be7cba1 (diff) | |
download | leetcode-88adbcc57a22112c6e45c61d3b1b77f315066b87.tar.gz leetcode-88adbcc57a22112c6e45c61d3b1b77f315066b87.zip |
3394. check if grid can be cut into sections
Diffstat (limited to 'check_grid_cut_section.py')
-rw-r--r-- | check_grid_cut_section.py | 60 |
1 files changed, 60 insertions, 0 deletions
diff --git a/check_grid_cut_section.py b/check_grid_cut_section.py new file mode 100644 index 0000000..b2869f7 --- /dev/null +++ b/check_grid_cut_section.py @@ -0,0 +1,60 @@ +# 3394. Check if Grid can be Cut into Sections + +""" +you are given an integer 'n' representing the dimensions of an 'n n' 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 +'[start_x, start_y, end_x, end_y]' representing a rectangle on the grid. 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 each of the three resulting formed by the cuts contains at least one +rectangle. every rectangle belongs to exactly one section. return 'true' if +such cuts can be made. otherwise, return 'false'. +""" + + +class Solution(object): + def checkValidCuts(self, n, rectangles): + """ + :type n: int + :type rectangles: List[List[int]] + :rtype: bool + """ + + def check(rectangles): + rectangles.sort() + res, pre = 0, rectangles[0][1] + for i, j in rectangles: + res += pre <= i + pre = max(pre, j) + return res > 1 + + return check([i[::2] for i in rectangles]) or check( + [i[1::2] for i in rectangles] + ) + + +if __name__ == "__main__": + obj = Solution() + print( + obj.checkValidCuts( + n=5, rectangles=[[1, 0, 5, 2], [0, 2, 2, 4], [3, 2, 5, 3], [0, 4, 4, 5]] + ) + ) + print( + obj.checkValidCuts( + n=4, rectangles=[[0, 0, 1, 1], [2, 0, 3, 4], [0, 2, 2, 3], [3, 0, 4, 3]] + ) + ) + print( + obj.checkValidCuts( + n=4, + rectangles=[ + [0, 2, 2, 4], + [1, 0, 3, 2], + [2, 2, 3, 4], + [3, 0, 4, 2], + [3, 2, 4, 4], + ], + ) + ) |