今日题目

https://leetcode.com/problems/check-if-grid-can-be-cut-into-sections

思路

这道题的核心在于区间合并。如果将问题压缩到一维，本质上就是：在这些区间中，是否存在两个以上的"间隔"？

解题方法

因此，我们可以对列表排序，然后遍历整个列表，判断当前区间与已遍历区间之间是否存在间隔。若存在间隔，则计数加一；否则将新区间合并进来。这个过程需要分别在水平方向和垂直方向各执行一次。

复杂度

  • 时间复杂度：$O(N)$，N 为 rectangles 的长度。
  • 空间复杂度：$O(1)$。

代码


class Solution:

    def checkValidCuts(self, n: int, rectangles: List[List[int]]) -> bool:

        N = len(rectangles)

        def get_res(a,b):

            rectangles.sort(key = lambda x: (x[a], x[b]))

            gapCnt,maxPos,l = 0,1,0

            while(l < N):

                while(l < N and rectangles[l][a] < maxPos):

                    maxPos = max(maxPos, rectangles[l][b])

                    l += 1

                if l == N:

                    break

                else:

                    gapCnt += 1

                    maxPos = rectangles[l][b]


                # print(a,l)


            if gapCnt > 1:

                return True

            return False


        return get_res(0,2) or get_res(1,3)