Skip to content
RED SAGSkills
hard60 ptsgeometrysorting

Total Area Covered by Windows

A screen-sharing tool needs to know how many pixels are covered by a set of overlapping windows, each an axis-aligned rectangle [x1, y1, x2, y2] with x1 < x2 and y1 < y2 (the rectangle covers x1 <= x < x2, y1 <= y < y2).

Return the area of the union of all rectangles: every point covered by at least one rectangle is counted once.

Example 1

Input: rects = [[0,0,2,2],[1,1,3,3]]
Output: 7
Explanation: 4 + 4 minus the 1 x 1 overlap.

Example 2

Input: rects = [[0,0,1,1],[0,0,1,1]]
Output: 1
Explanation: Same rectangle twice still covers only 1.

Constraints

  • 0 <= rects.length <= 200
  • -10^6 <= coordinates <= 10^6, integers
Hint 1

Sort all distinct x coordinates; between two neighbours, the set of covering rectangles is fixed.

Hint 2

For each vertical strip, merge the y intervals of the rectangles that span it.

Discussion 0

Join free to post in the discussion.

Good practice for: Game Developer, Frontend Developer, Embedded Systems Engineer, Backend Developer, Data Scientist

Run checks your code on 3 sample tests. Submit runs all 9 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.