3394. Check if Grid can be Cut into Sections - Medium

前往題目

想法

• 不知該如何檢查是否可切成三塊

思路

看成是intervals來解

1. 分成x和y座標並排序
2. 垂直和水平方向分開來檢查是否重疊，並記錄不重疊數
3. 輸出結果

Code

class Solution {
    public boolean checkValidCuts(int n, int[][] rectangles) {
        int[][] x = new int[rectangles.length][2];
        int[][] y = new int[rectangles.length][2];

        // Build x and y coordinates array, so that we can check horizontally and vertically
        for (int i = 0; i < rectangles.length; ++i) {
            x[i][0] = rectangles[i][0];
            x[i][1] = rectangles[i][2];
            y[i][0] = rectangles[i][1];
            y[i][1] = rectangles[i][3];
        }

        Arrays.sort(x, (a, b) -> a[0] - b[0]);
        Arrays.sort(y, (a, b) -> a[0] - b[0]);
        
        return Math.max(checkNonOverlapping(x), checkNonOverlapping(y)) >= 3;
    }

    private int checkNonOverlapping(int[][] intervals) {
        int count = 0;
        int prevEnd = -1;

        // Start checking overlapping
        for (int i = 0; i < intervals.length; ++i) {
            int start = intervals[i][0];
            int end = intervals[i][1];

            // When non-overlapping
            if (prevEnd <= start) {
                ++count;
            }

            prevEnd = Math.max(prevEnd, end);
        }

        return count;
    }
}