Medium

题目描述

给你一个整数 n 表示 n x n 网格的尺寸，网格的原点在左下角。还给你一个二维坐标数组 rectangles，其中 rectangles[i] 的格式为 [startx, starty, endx, endy]，表示网格上的一个矩形。每个矩形定义如下：

  • (startx, starty)：矩形的左下角
  • (endx, endy)：矩形的右上角

注意矩形不会重叠。你的任务是确定是否可以在网格上进行两次水平切割或两次垂直切割，使得：

  • 切割形成的三个部分每个都至少包含一个矩形
  • 每个矩形恰好属于一个部分

如果可以进行这样的切割，返回 true；否则返回 false。

示例 1：

输入：n = 5, rectangles = [[1,0,5,2],[0,2,2,4],[3,2,5,3],[0,4,4,5]]
输出：true
解释：我们可以在 y = 2 和 y = 4 处进行水平切割。

示例 2：

输入：n = 4, rectangles = [[0,0,1,1],[2,0,3,4],[0,2,2,3],[3,0,4,3]]
输出：true
解释：我们可以在 x = 2 和 x = 3 处进行垂直切割。

示例 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
解释：无法进行满足条件的两次水平或垂直切割。

约束条件：

  • 3 <= n <= 10^9
  • 3 <= rectangles.length <= 10^5
  • 0 <= rectangles[i][0] < rectangles[i][2] <= n
  • 0 <= rectangles[i][1] < rectangles[i][3] <= n
  • 矩形不会重叠

解题思路

这道题的关键思路是将二维切割问题转化为一维区间分割问题。

核心思想：

  1. 分别考虑水平切割和垂直切割两种情况
  2. 对于水平切割，将每个矩形投影到 y 轴上，得到区间 [starty, endy]
  3. 对于垂直切割，将每个矩形投影到 x 轴上，得到区间 [startx, endx]
  4. 问题转化为：能否找到两个切割点，将这些区间分成三组，每组至少包含一个区间

算法步骤：

  1. 对于 x 和 y 方向，分别提取所有矩形的投影区间
  2. 对区间按起始位置排序
  3. 使用贪心策略合并重叠区间，得到若干个不相交的连续段
  4. 如果连续段数量 ≥ 3，说明可以进行两次切割分成三部分

贪心策略： 遍历排序后的区间，维护当前连续段的结束位置。如果下一个区间的起始位置大于当前结束位置，则形成新的连续段。

这种方法的优势是将复杂的二维几何问题简化为一维区间问题，时间复杂度为 O(n log n)，主要消耗在排序上。

代码实现

class Solution {
public:
    bool checkValidCuts(int n, vector<vector<int>>& rectangles) {
        return canCut(rectangles, 0) || canCut(rectangles, 1);
    }
    
private:
    bool canCut(vector<vector<int>>& rectangles, int direction) {
        vector<pair<int, int>> intervals;
        
        for (auto& rect : rectangles) {
            if (direction == 0) { // vertical cuts (x direction)
                intervals.push_back({rect[0], rect[2]});
            } else { // horizontal cuts (y direction)
                intervals.push_back({rect[1], rect[3]});
            }
        }
        
        sort(intervals.begin(), intervals.end());
        
        int segments = 1;
        int currentEnd = intervals[0].second;
        
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i].first >= currentEnd) {
                segments++;
                currentEnd = intervals[i].second;
            } else {
                currentEnd = max(currentEnd, intervals[i].second);
            }
        }
        
        return segments >= 3;
    }
};

class Solution:
    def checkValidCuts(self, n: int, rectangles: List[List[int]]) -> bool:
        def can_cut(direction):
            intervals = []
            
            for rect in rectangles:
                if direction == 0:  # vertical cuts (x direction)
                    intervals.append((rect[0], rect[2]))
                else:  # horizontal cuts (y direction)
                    intervals.append((rect[1], rect[3]))
            
            intervals.sort()
            
            segments = 1
            current_end = intervals[0][1]
            
            for i in range(1, len(intervals)):
                if intervals[i][0] >= current_end:
                    segments += 1
                    current_end = intervals[i][1]
                else:
                    current_end = max(current_end, intervals[i][1])
            
            return segments >= 3
        
        return can_cut(0) or can_cut(1)

public class Solution {
    public bool CheckValidCuts(int n, int[][] rectangles) {
        return CanCut(rectangles, 0) || CanCut(rectangles, 1);
    }
    
    private bool CanCut(int[][] rectangles, int direction) {
        var intervals = new List<(int, int)>();
        
        foreach (var rect in rectangles) {
            if (direction == 0) { // vertical cuts (x direction)
                intervals.Add((rect[0], rect[2]));
            } else { // horizontal cuts (y direction)
                intervals.Add((rect[1], rect[3]));
            }
        }
        
        intervals.Sort();
        
        int segments = 1;
        int currentEnd = intervals[0].Item2;
        
        for (int i = 1; i < intervals.Count; i++) {
            if (intervals[i].Item1 >= currentEnd) {
                segments++;
                currentEnd = intervals[i].Item2;
            } else {
                currentEnd = Math.Max(currentEnd, intervals[i].Item2);
            }
        }
        
        return segments >= 3;
    }
}

var checkValidCuts = function(n, rectangles) {
    // Check vertical cuts
    const xIntervals = rectangles.map(r => [r[0], r[2]]);
    xIntervals.sort((a, b) => a[0] - b[0]);
    
    let verticalSections = 1;
    let currentEnd = xIntervals[0][1];
    
    for (let i = 1; i < xIntervals.length; i++) {
        if (xIntervals[i][0] >= currentEnd) {
            verticalSections++;
            currentEnd = xIntervals[i][1];
        } else {
            currentEnd = Math.max(currentEnd, xIntervals[i][1]);
        }
    }
    
    if (verticalSections >= 3) return true;
    
    // Check horizontal cuts
    const yIntervals = rectangles.map(r => [r[1], r[3]]);
    yIntervals.sort((a, b) => a[0] - b[0]);
    
    let horizontalSections = 1;
    currentEnd = yIntervals[0][1];
    
    for (let i = 1; i < yIntervals.length; i++) {
        if (yIntervals[i][0] >= currentEnd) {
            horizontalSections++;
            currentEnd = yIntervals[i][1];
        } else {
            currentEnd = Math.max(currentEnd, yIntervals[i][1]);
        }
    }
    
    return horizontalSections >= 3;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n log n)，其中 n 是矩形数量，主要消耗在排序上
空间复杂度O(n)，存储区间数组