3394. Check if Grid can be Cut into Sections
Approach
Sort rectangles by x or y; check if projections allow ≥ 2 gaps (forming 3 sections).
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Greedy algorithms make locally optimal choices at each step, hoping to reach a global optimum. Greedy works when a problem has the "greedy choice property" and "optimal substructure". Common applications: interval scheduling, activity selection, Huffman coding, and jump game.
Sorting is often a preprocessing step that enables binary search, two-pointer sweeps, or greedy algorithms. C#'s Array.Sort() uses an introspective sort (O(n log n)). Custom comparisons use the Comparison<T> delegate or IComparer<T>. Consider counting sort or bucket sort for bounded integer inputs.
// Approach: Sort rectangles by x or y; check if projections allow ≥ 2 gaps (forming 3 sections).
// Time: O(n log n) Space: O(1)
public class Solution
{
public bool CheckValidCuts(int n, int[][] rectangles)
{
int[][] xs = new int[rectangles.Length][];
int[][] ys = new int[rectangles.Length][];
for (int i = 0; i < rectangles.Length; ++i)
{
xs[i] = new int[2];
xs[i][0] = rectangles[i][0];
xs[i][1] = rectangles[i][2];
ys[i] = new int[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;
Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));
foreach (var interval in intervals)
{
int start = interval[0];
int end = interval[1];
if (start < prevEnd)
prevEnd = Math.Max(prevEnd, end);
else
{
prevEnd = end;
++count;
}
}
return count;
}
}