题目描述

给你一个整数 n 表示一个 n x n 的网格图，坐标原点是这个网格图的左下角。同时给你一个二维坐标数组 rectangles，其中 rectangles[i] 的格式为 [start_x, start_y, end_x, end_y]，表示网格图中的一个矩形。每个矩形定义如下：

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

注意，矩形相互之间不会重叠。你的任务是判断是否能找到两条 要么都垂直要么都水平 的 两条切割线，满足：

• 切割得到的三个部分分别都 至少 包含一个矩形。
• 每个矩形都 恰好仅 属于一个切割得到的部分。

如果可以得到这样的切割，请你返回 true，否则返回 false。

样例

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

输出：true

解释：

网格图如下所示，我们可以在 y = 2 和 y = 4 处进行水平切割，所以返回 true。

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

输出：true

解释：

我们可以在 x = 2 和 x = 3 处进行竖直切割，所以返回 true。

输入：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 <= n <= 10^9
• 3 <= rectangles.length <= 10^5
• 0 <= rectangles[i][0] < rectangles[i][2] <= n
• 0 <= rectangles[i][1] < rectangles[i][3] <= n
• 矩形之间两两不会有重叠。

算法

(排序，线段重叠) $O(n \log n)$

1. 将每个矩形分为竖直和水平两个方向的线段，针对对于每个方向单独讨论。
2. 问题转为给定一系列的线段，是否存在两个点，可以将所有线段分为三部分。
3. 对每个方向的线段按照起始坐标进行排序，遍历线段。遍历过程中，记录当前的最远终止距离 $end$，如果新的线段的起始位置大于等于 $end$，则新的线段的起始位置和 $end$ 之间就有一个合法的分割点。

时间复杂度

• 预处理线段的时间复杂度为 $O(n)$，排序求解的时间复杂度为 $O(n \log n)$。
• 故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储线段以及排序的系统栈。

C++ 代码

class Solution {
private:
    bool solve(vector<pair<int, int>> &segs) {
        const int n = segs.size();

        sort(segs.begin(), segs.end());

        int end = segs[0].second, cnt = 0;

        for (int i = 1; i < n; i++) {
            if (end <= segs[i].first) {
                ++cnt;
                if (cnt == 2)
                    return true;
            }

            end = max(end, segs[i].second);
        }

        return false;
    }

public:
    bool checkValidCuts(int n, vector<vector<int>>& rectangles) {
        vector<pair<int, int>> h, v;

        for (const auto &rec : rectangles) {
            v.emplace_back(rec[0], rec[2]);
            h.emplace_back(rec[1], rec[3]);
        }

        return solve(v) || solve(h);
    }
};