Skip to content

3394. Check if Grid can be Cut into Sections 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(\texttt{sort})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
 public:
  bool checkValidCuts(int n, vector<vector<int>>& rectangles) {
    vector<pair<int, int>> xs;
    vector<pair<int, int>> ys;

    for (const vector<int> rectangles : rectangles) {
      const int startX = rectangles[0];
      const int startY = rectangles[1];
      const int endX = rectangles[2];
      const int endY = rectangles[3];
      xs.emplace_back(startX, endX);
      ys.emplace_back(startY, endY);
    }

    return max(countMerged(xs), countMerged(ys)) >= 3;
  }

 private:
  int countMerged(vector<pair<int, int>>& intervals) {
    int count = 0;
    int prevEnd = 0;

    ranges::sort(intervals);

    for (const auto& [start, eend] : intervals)
      if (start < prevEnd) {
        prevEnd = max(prevEnd, eend);
      } else {
        prevEnd = eend;
        ++count;
      }

    return count;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
  public boolean checkValidCuts(int n, int[][] rectangles) {
    int[][] xs = new int[rectangles.length][2];
    int[][] ys = new int[rectangles.length][2];

    for (int i = 0; i < rectangles.length; ++i) {
      xs[i][0] = rectangles[i][0];
      xs[i][1] = rectangles[i][2];
      ys[i][0] = rectangles[i][1];
      ys[i][1] = rectangles[i][3];
    }

    return Math.max(countMerged(xs), countMerged(ys)) >= 3;
  }

  private int countMerged(int[][] intervals) {
    int count = 0;
    int prevEnd = 0;

    Arrays.sort(intervals, Comparator.comparingInt((int[] interval) -> interval[0]));

    for (int[] interval : intervals) {
      final int start = interval[0];
      final int end = interval[1];
      if (start < prevEnd) {
        prevEnd = Math.max(prevEnd, end);
      } else {
        prevEnd = end;
        ++count;
      }
    }

    return count;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def checkValidCuts(self, n: int, rectangles: list[list[int]]) -> bool:
    xs = [(startX, endX) for startX, _, endX, _ in rectangles]
    ys = [(startY, endY) for _, startY, _, endY in rectangles]
    return max(self._countMerged(xs),
               self._countMerged(ys)) >= 3

  def _countMerged(self, intervals: list[tuple[int, int]]) -> int:
    count = 0
    prevEnd = 0
    for start, end in sorted(intervals):
      if start < prevEnd:
        prevEnd = max(prevEnd, end)
      else:
        prevEnd = end
        count += 1
    return count