Create Check if Grid can be Cut into Sections.py

erjan · web-flow · commit ce61cff8c3f2 · 2025-03-26T02:10:26.000+05:00
diff --git a/Check if Grid can be Cut into Sections.py b/Check if Grid can be Cut into Sections.py
@@ -0,0 +1,31 @@
+You are given an integer n representing the dimensions of an n x 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 [startx, starty, endx, endy], representing a rectangle on the grid. Each rectangle is defined as follows:
+
+(startx, starty): The bottom-left corner of the rectangle.
+(endx, endy): The top-right corner of the rectangle.
+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 sections 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:
+    def checkValidCuts(self, n: int, rectangles: List[List[int]]) -> bool:
+        def check(intervals):
+            intervals.sort()
+            
+            sections = 0
+            max_end = intervals[0][1]
+            
+            for start, end in intervals:
+                if max_end <= start:
+                    sections += 1
+                max_end = max(max_end, end)
+                
+            return sections >= 2
+        
+        x_intervals = [[rect[0], rect[2]] for rect in rectangles]
+        y_intervals = [[rect[1], rect[3]] for rect in rectangles]
+        
+        return check(x_intervals) or check(y_intervals)
