'2025/03/25'에 해당되는 글 1건

Leetcode Problem:

• Check if Grid can be Cut into Sections

Summary

• Problem: Determine if it is possible to make two horizontal or two vertical cuts on an n x n grid such that each cut contains at least one rectangle and every rectangle belongs to exactly one section.

Approach

• The solution uses a two-dimensional approach, trying both horizontal and vertical cuts
• It sorts the rectangles by their starting coordinate in the given dimension and tracks the furthest ending coordinate seen so far
• It then checks for gaps between rectangles where a cut can be made
• The solution returns true if at least two gaps are found, indicating that valid cuts can be made.

Complexity

• O(n log n) due to sorting the rectangles, where n is the number of rectangles.

Explanation

• The solution first tries both horizontal and vertical cuts using the `checkCuts` function, which takes a 2D array of rectangles and a dimension (0 for horizontal cuts and 1 for vertical cuts) as input
• The `checkCuts` function sorts the rectangles by their starting coordinate in the given dimension and tracks the furthest ending coordinate seen so far
• It then checks for gaps between rectangles where a cut can be made
• The function returns true if at least two gaps are found, indicating that valid cuts can be made.

Solution Code:

class Solution {
public:
    bool checkValidCuts(int n, vector>& rectangles) {
        // Try both horizontal and vertical cuts
        return checkCuts(rectangles, 0) || checkCuts(rectangles, 1);
    }

private:
    // Check if valid cuts can be made in a specific dimension
    bool checkCuts(vector>& rectangles, int dim) {
        int gapCount = 0;

        // Sort rectangles by their starting coordinate in the given dimension
        sort(rectangles.begin(), rectangles.end(),
             [dim](const vector& a, const vector& b) {
                 return a[dim] < b[dim];
             });

        // Track the furthest ending coordinate seen so far
        int furthestEnd = rectangles[0][dim + 2];

        for (size_t i = 1; i < rectangles.size(); i++) {
            vector& rect = rectangles[i];

            // If current rectangle starts after the furthest end we've seen,
            // we found a gap where a cut can be made
            if (furthestEnd <= rect[dim]) {
                gapCount++;
            }

            // Update the furthest ending coordinate
            furthestEnd = max(furthestEnd, rect[dim + 2]);
        }

        // We need at least 2 gaps to create 3 sections
        return gapCount >= 2;
    }
};