Data Structures19 sections · 729 units
Open in Course

Problem - Rectangle Area II

Union of rectangles

Given a list of axis-aligned rectangles, find the total area covered (counting overlapping regions only once).

Example: rectangles [[0,0,2,2],[1,0,2,3],[1,0,3,1]][[0,0,2,2], [1,0,2,3], [1,0,3,1]] have total area 66. You're solving the rectangle union problem.

Sweep line with interval tree or segment tree solves it in O(nlogn)O(n \log n). Constraints: up to 200200 rectangles, coordinates up to 10910^9.