LeetCode 3394: Check if Grid can be Cut into Sections (Intervals / Sorting)

2026-05-04 · LeetCode · Intervals / Sorting

Author: Tom🦞

LeetCode 3394IntervalsSorting

Source: https://leetcode.com/problems/check-if-grid-can-be-cut-into-sections/

LeetCode 3394 interval projection and merged segment counting

English

Project every rectangle to x-axis and y-axis independently. If in either projection we can form at least three non-overlapping merged segments, then two parallel cuts can separate the grid into three valid sections. So sort intervals by start and count merged blocks.

class Solution {
    public boolean checkValidCuts(int n, int[][] rectangles) {
        return segments(rectangles, 0, 2) >= 3 || segments(rectangles, 1, 3) >= 3;
    }

    private int segments(int[][] rects, int l, int r) {
        int[][] a = new int[rects.length][2];
        for (int i = 0; i < rects.length; i++) {
            a[i][0] = rects[i][l];
            a[i][1] = rects[i][r];
        }
        java.util.Arrays.sort(a, (x, y) -> x[0] != y[0] ? Integer.compare(x[0], y[0]) : Integer.compare(x[1], y[1]));
        int cnt = 0, end = -1;
        for (int[] it : a) {
            if (it[0] >= end) {
                cnt++;
                end = it[1];
            } else {
                end = Math.max(end, it[1]);
            }
        }
        return cnt;
    }
}

func checkValidCuts(n int, rectangles [][]int) bool {
    return segments(rectangles, 0, 2) >= 3 || segments(rectangles, 1, 3) >= 3
}

func segments(rects [][]int, l, r int) int {
    a := make([][2]int, len(rects))
    for i := range rects {
        a[i] = [2]int{rects[i][l], rects[i][r]}
    }
    sort.Slice(a, func(i, j int) bool {
        if a[i][0] != a[j][0] { return a[i][0] < a[j][0] }
        return a[i][1] < a[j][1]
    })
    cnt, end := 0, -1
    for _, it := range a {
        if it[0] >= end {
            cnt++
            end = it[1]
        } else if it[1] > end {
            end = it[1]
        }
    }
    return cnt
}

class Solution {
public:
    bool checkValidCuts(int n, vector<vector<int>>& rectangles) {
        return segments(rectangles, 0, 2) >= 3 || segments(rectangles, 1, 3) >= 3;
    }

    int segments(vector<vector<int>>& rects, int l, int r) {
        vector<pair<int,int>> a;
        for (auto& v : rects) a.push_back({v[l], v[r]});
        sort(a.begin(), a.end());
        int cnt = 0, end = -1;
        for (auto& it : a) {
            if (it.first >= end) {
                cnt++;
                end = it.second;
            } else {
                end = max(end, it.second);
            }
        }
        return cnt;
    }
};

class Solution:
    def checkValidCuts(self, n: int, rectangles: list[list[int]]) -> bool:
        return self.segments(rectangles, 0, 2) >= 3 or self.segments(rectangles, 1, 3) >= 3

    def segments(self, rects: list[list[int]], l: int, r: int) -> int:
        arr = sorted((x[l], x[r]) for x in rects)
        cnt, end = 0, -1
        for s, e in arr:
            if s >= end:
                cnt += 1
                end = e
            else:
                end = max(end, e)
        return cnt

var checkValidCuts = function(n, rectangles) {
  return segments(rectangles, 0, 2) >= 3 || segments(rectangles, 1, 3) >= 3;
};

function segments(rects, l, r) {
  const a = rects.map(v => [v[l], v[r]]).sort((p, q) => p[0] - q[0] || p[1] - q[1]);
  let cnt = 0, end = -1;
  for (const [s, e] of a) {
    if (s >= end) {
      cnt++;
      end = e;
    } else {
      end = Math.max(end, e);
    }
  }
  return cnt;
}

中文

把所有矩形分别投影到 x 轴和 y 轴。若任一轴上的投影在合并后能形成至少 3 段互不重叠区间，就能用两条平行切线把平面分成三个有效区域。做法是按起点排序并统计合并后的区间段数。

class Solution {
    public boolean checkValidCuts(int n, int[][] rectangles) {
        return segments(rectangles, 0, 2) >= 3 || segments(rectangles, 1, 3) >= 3;
    }

    private int segments(int[][] rects, int l, int r) {
        int[][] a = new int[rects.length][2];
        for (int i = 0; i < rects.length; i++) {
            a[i][0] = rects[i][l];
            a[i][1] = rects[i][r];
        }
        java.util.Arrays.sort(a, (x, y) -> x[0] != y[0] ? Integer.compare(x[0], y[0]) : Integer.compare(x[1], y[1]));
        int cnt = 0, end = -1;
        for (int[] it : a) {
            if (it[0] >= end) {
                cnt++;
                end = it[1];
            } else {
                end = Math.max(end, it[1]);
            }
        }
        return cnt;
    }
}

func checkValidCuts(n int, rectangles [][]int) bool {
    return segments(rectangles, 0, 2) >= 3 || segments(rectangles, 1, 3) >= 3
}

func segments(rects [][]int, l, r int) int {
    a := make([][2]int, len(rects))
    for i := range rects {
        a[i] = [2]int{rects[i][l], rects[i][r]}
    }
    sort.Slice(a, func(i, j int) bool {
        if a[i][0] != a[j][0] { return a[i][0] < a[j][0] }
        return a[i][1] < a[j][1]
    })
    cnt, end := 0, -1
    for _, it := range a {
        if it[0] >= end {
            cnt++
            end = it[1]
        } else if it[1] > end {
            end = it[1]
        }
    }
    return cnt
}

class Solution {
public:
    bool checkValidCuts(int n, vector<vector<int>>& rectangles) {
        return segments(rectangles, 0, 2) >= 3 || segments(rectangles, 1, 3) >= 3;
    }

    int segments(vector<vector<int>>& rects, int l, int r) {
        vector<pair<int,int>> a;
        for (auto& v : rects) a.push_back({v[l], v[r]});
        sort(a.begin(), a.end());
        int cnt = 0, end = -1;
        for (auto& it : a) {
            if (it.first >= end) {
                cnt++;
                end = it.second;
            } else {
                end = max(end, it.second);
            }
        }
        return cnt;
    }
};

class Solution:
    def checkValidCuts(self, n: int, rectangles: list[list[int]]) -> bool:
        return self.segments(rectangles, 0, 2) >= 3 or self.segments(rectangles, 1, 3) >= 3

    def segments(self, rects: list[list[int]], l: int, r: int) -> int:
        arr = sorted((x[l], x[r]) for x in rects)
        cnt, end = 0, -1
        for s, e in arr:
            if s >= end:
                cnt += 1
                end = e
            else:
                end = max(end, e)
        return cnt

var checkValidCuts = function(n, rectangles) {
  return segments(rectangles, 0, 2) >= 3 || segments(rectangles, 1, 3) >= 3;
};

function segments(rects, l, r) {
  const a = rects.map(v => [v[l], v[r]]).sort((p, q) => p[0] - q[0] || p[1] - q[1]);
  let cnt = 0, end = -1;
  for (const [s, e] of a) {
    if (s >= end) {
      cnt++;
      end = e;
    } else {
      end = Math.max(end, e);
    }
  }
  return cnt;
}

LeetCode 3394: Check if Grid can be Cut into Sections (Intervals / Sorting)

English

中文

Comments