Count Rectangle Coverage on a Grid

Problem Statement

Given an integer n representing the dimensions of an n x n 2D grid initialized to all zeros, and an array of rectangles rectangles, return the final grid where each cell (r, c) contains the number of rectangles covering that cell.

Each rectangle is represented as a 4-element list [r1, c1, r2, c2], indicating the top-left coordinate (r1, c1) and the bottom-right coordinate (r2, c2) inclusive. A cell (r, c) is covered by a rectangle if r1 <= r <= r2 and c1 <= c <= c2.

Your solution should be non-mutating (do not modify the input list of rectangles) and must handle large numbers of updates efficiently.

Function Signature

def count_coverage(n: int, rectangles: list[list[int]]) -> list[list[int]]:
    pass

Constraints

• 1 <= n <= 1000
• 0 <= len(rectangles) <= 10^5
• rectangles[i] has length 4
• 0 <= r1 <= r2 < n
• 0 <= c1 <= c2 < n

Examples

Example 1

Input: n = 3, rectangles = [[0, 0, 1, 1], [1, 1, 2, 2]]
Output:
[
  [1, 1, 0],
  [1, 2, 1],
  [0, 1, 1]
]
Explanation:
- The first rectangle covers (0,0), (0,1), (1,0), (1,1).
- The second rectangle covers (1,1), (1,2), (2,1), (2,2).
- Cell (1, 1) is overlapped by both rectangles, yielding a count of 2.

Example 2

Input: n = 2, rectangles = []
Output:
[
  [0, 0],
  [0, 0]
]
Explanation: No rectangles are provided, so every cell retains a coverage count of 0.

Edge Cases

• rectangles is empty (len(rectangles) == 0).
• Single-cell rectangles where r1 == r2 and c1 == c2.
• Full-grid coverage where [r1, c1, r2, c2] = [0, 0, n - 1, n - 1].
• Duplicate rectangle entries in rectangles (each duplicate must contribute to the count independently).