Check if Grid can be Cut into Sections

Problem Description

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] = [startx, starty, endx, endy] represents 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.

Conditions to Satisfy:

Your task is to determine if it is possible to make either two horizontal or two vertical cuts on the grid such that:

1. Each of the three resulting sections formed by the cuts contains at least one rectangle.
2. Every rectangle belongs to exactly one section (i.e., no rectangle spans across a cut).

Return:

• true if such cuts can be made.
• false otherwise.

---

Examples & Explanation

Example 1

Input:

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

Grid Representation:

Explanation:

We can make horizontal cuts at y = 2 and y = 4, forming three sections:

• Section 1: Below y = 2 (contains R1)
• Section 2: Between y = 2 and y = 4 (contains R2 and R3)
• Section 3: Above y = 4 (contains R4)

Since all conditions are satisfied, output is true.

Constraints

$$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$$

Rectangles do not overlap.