題目資訊

題目編號: 3394
題目連結: Check if Grid can be Cut into Sections
主題: Array, Sorting

題目敘述

你有一個整數 n，代表 $n \times n$ 網格的尺寸，原點位於網格的左下角。你還有一個二維座標陣列 rectangles，其中 rectangles[i] 的形式為 $[start_x, start_y, end_x, end_y]$，代表網格上的一個矩形。每個矩形定義如下：

$(start_x, start_y)$：矩形的左下角。
$(end_x, end_y)$：矩形的右上角。

注意矩形之間不會重疊。你的任務是判斷是否可以在網格上進行兩條水平或兩條垂直切割，使得：

切割後形成的三個區域中的每一個包含至少一個矩形。
每個矩形恰好屬於一個區域。

如果可以進行這樣的切割，返回 true；否則，返回 false。

範例 1：

輸入： n = 5, rectangles = [[1,0,5,2],[0,2,2,4],[3,2,5,3],[0,4,4,5]]

輸出： true

解釋：

範例 1 圖解

圖中展示了網格。我們可以在 y = 2 和 y = 4 進行水平切割。因此，輸出是 true。

範例 2：

輸入： n = 4, rectangles = [[0,0,1,1],[2,0,3,4],[0,2,2,3],[3,0,4,3]]

輸出： true

解釋：

範例 2 圖解

我們可以在 x = 2 和 x = 3 進行垂直切割。因此，輸出是 true。

範例 3：

輸入： n = 4, rectangles = [[0,2,2,4],[1,0,3,2],[2,2,3,4],[3,0,4,2],[3,2,4,4]]

輸出： false

解釋：

我們無法進行符合條件的兩條水平或垂直切割。因此，輸出是 false。

約束條件：

$3 \leq n \leq 10^9$
$3 \leq \text{rectangles.length} \leq 10^5$
$0 \leq \text{rectangles}[i][0] < \text{rectangles}[i][2] \leq n$
$0 \leq \text{rectangles}[i][1] < \text{rectangles}[i][3] \leq n$
任何兩個矩形不重疊。

直覺

此問題涉及判斷能否在一個大小為 ( n \times n ) 的網格中將一組不重疊的矩形劃分為三個連續的區域。約束條件是需要做出兩個水平或兩個垂直的切割，同時確保每個區域至少包含一個矩形，且每個矩形不能跨越兩個區域。在給定這些條件的情況下，一個自然的方法是檢視潛在的水平和垂直線作為切割點，並根據規定的標準檢查它們的有效性。

解法

解法利用了一種掃描線技巧，分析基於矩形邊界的潛在切割線。我們關注的是識別出可以放置切割的位置，使得它們能夠將矩形清晰地分割成三個或更多的區域。

提取關鍵點： 首先，我們識別矩形的關鍵 x 和 y 座標，這些座標表示矩形的水平和垂直邊界。對於每個矩形，我們考慮其起始和結束座標以確定潛在的切割點。我們還記錄最大 x 和 y 座標以確保不會嘗試越過網格邊界進行切割。
存儲並排序邊界： 一旦識別出關鍵點，將這些信息存入兩個分別用於水平和垂直邊界的列表中。我們使用負值來表示矩形邊界的結束。通過絕對座標值對這些列表進行排序，允許我們從最小到最大的遍歷，從而適當地考慮潛在的切割線。
確定有效的切割：
- 我們在排序後的列表中遍歷，保持一個活動塊計數器，以確定一條線當前是否穿過任何矩形。
- 當橫向或縱向的線段符合以下條件時，視之為有效切割：
  - 活動塊計數器回到零，這表明矩形之間的潛在切割。
  - 切割不在最大 x 或 y 邊界。
- 如果在水平或垂直遍歷中識別了兩個這樣的切割，我們立即返回 true，表示有效地分割。
評估並總結： 如果經過完整評估後，無論是水平還是垂直切割均不滿足條件，方法返回 false，這表明不可能按照規定將所有矩形分割成三個獨立的區域。

此方法通過利用已排序的邊界特性高效地檢查可能的切割，確保解決方案在輸入約束內是最優的。

程式碼

C++

class Solution {
public:
    bool checkValidCuts(int n, vector<vector<int>>& rectangles) {
        int horzMax = INT_MIN, vertMax = INT_MIN;
        vector<int> horz, vert;

        // 從矩形中提取邊緣並追蹤最大 x 和 y
        for (vector<int>& rect : rectangles) {
            horzMax = max(horzMax, rect[2]);
            vertMax = max(vertMax, rect[3]);
            horz.push_back(rect[0]);
            vert.push_back(rect[1]);
            horz.push_back(-rect[2]);
            vert.push_back(-rect[3]);
        }
        
        // 排序邊緣以檢查可能的切割
        sort(horz.begin(), horz.end(), [](const int& a, const int& b) {
            if (abs(a) != abs(b)) return abs(a) < abs(b);
            else return a < b;
        });
        sort(vert.begin(), vert.end(), [](const int& a, const int& b) {
            if (abs(a) != abs(b)) return abs(a) < abs(b);
            else return a < b;
        });

        // 檢查水平切割
        int horzCuts = 0, activeHorzBlocks = 0;
        for (int i = 0; i < horz.size(); i++) {
            // 調整活動區塊計數器
            if (horz[i] < 0) activeHorzBlocks--;
            else activeHorzBlocks++;
            
            // 檢查此點是否適合切割
            if (activeHorzBlocks == 0 && -horz[i] != horzMax) horzCuts++;
            if (horzCuts >= 2) return true;
        }

        // 檢查垂直切割
        int vertCuts = 0, activeVertBlocks = 0;
        for (int i = 0; i < vert.size(); i++) {
            // 調整活動區塊計數器
            if (vert[i] < 0) activeVertBlocks--;
            else activeVertBlocks++;
            
            // 檢查此點是否適合切割
            if (activeVertBlocks == 0 && -vert[i] != vertMax) vertCuts++;
            if (vertCuts >= 2) return true;
        }

        // 如果水平和垂直切割都不合適，返回 false
        return false;
    }
};

Python

class Solution:
    def checkValidCuts(self, n, rectangles):
        horzMax = float('-inf')
        vertMax = float('-inf')
        horz = []
        vert = []

        # 從矩形提取邊並記錄最大 x 和 y
        for rect in rectangles:
            horzMax = max(horzMax, rect[2])
            vertMax = max(vertMax, rect[3])
            horz.append(rect[0])
            vert.append(rect[1])
            horz.append(-rect[2])
            vert.append(-rect[3])
        
        # 排序邊以檢查可能的切割
        horz.sort(key=lambda a: (abs(a), a))
        vert.sort(key=lambda a: (abs(a), a))

        # 檢查水平切割
        horzCuts = 0
        activeHorzBlocks = 0
        for i in range(len(horz)):
            # 調整活躍區塊計數器
            if horz[i] < 0:
                activeHorzBlocks -= 1
            else:
                activeHorzBlocks += 1
            
            # 檢查該點是否有效以進行切割
            if activeHorzBlocks == 0 and -horz[i] != horzMax:
                horzCuts += 1
            if horzCuts >= 2:
                return True

        # 檢查垂直切割
        vertCuts = 0
        activeVertBlocks = 0
        for i in range(len(vert)):
            # 調整活躍區塊計數器
            if vert[i] < 0:
                activeVertBlocks -= 1
            else:
                activeVertBlocks += 1
            
            # 檢查該點是否有效以進行切割
            if activeVertBlocks == 0 and -vert[i] != vertMax:
                vertCuts += 1
            if vertCuts >= 2:
                return True

        # 如果既沒有水平切割也沒有垂直切割有效則返回 false
        return False

複雜度分析

時間複雜度: $O(m \log m)$
1. 遍歷矩形的迴圈:
  - 迴圈遍歷每個矩形以收集邊緣資訊。如果有 $m$ 個矩形，這一步驟需花費 $O(m)$ 的時間。
2. 排序邊緣:
  - 列表 horz 和 vert 各自被填入兩倍於矩形數量的條目（每個矩形兩個條目）。因此，每個列表的長度為 $2m$。
  - 分別對兩個列表進行排序需 $O(m \log m)$ 的時間，因為排序需要 $O(n \log n)$ 的時間複雜度，其中 $n$ 是需要排序的元素數量。
3. 檢查水平和垂直切割:
  - 用於檢查有效的水平和垂直切割的迴圈遍歷已排序的列表，每個列表包含 $2m$ 個元素。因此，每個迴圈的運行時間為 $O(m)$。
  - 因此，切割檢查總共需 $O(m)$。
主要的時間複雜度來自排序步驟，這使得完整算法的時間複雜度為 $O(m \log m)$。
空間複雜度: $O(m)$
1. 用於邊緣列表的空間:
  - 列表 horz 和 vert 各自包含 $2m$ 個整數，其中 $m$ 是矩形的數量。
2. 輔助存儲空間:
  - 排序操作和邊緣列表需要與列表大小成比例的額外存儲空間。
整體空間複雜度由邊緣列表所需的空間決定，即 $O(m)$。

CS Note
En

Leetcode 3394. Check if Grid can be Cut into Sections

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析