Rectangle Area II

hard sweep-line intervals geometry

Problem

Given a list of axis-aligned rectangles, return the total area covered by the union, modulo 10^9 + 7.

Inputrectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]

Output6

The union covers 6 square units.

input

def rectangleArea(rectangles):
    MOD = 10**9 + 7
    events = []
    for x1, y1, x2, y2 in rectangles:
        events.append((x1, 1, y1, y2))
        events.append((x2, -1, y1, y2))
    events.sort()
    active = []
    prev_x = events[0][0]
    area = 0
    def covered():
        cov = 0; cur = -1
        for a, b in sorted(active):
            cur = max(cur, a)
            cov += max(0, b - cur)
            cur = max(cur, b)
        return cov
    for x, sig, y1, y2 in events:
        area += covered() * (x - prev_x)
        if sig == 1: active.append((y1, y2))
        else: active.remove((y1, y2))
        prev_x = x
    return area % MOD

function rectangleArea(rectangles) {
  const MOD = 1000000007n;
  const events = [];
  for (const [x1, y1, x2, y2] of rectangles) {
    events.push([x1, 1, y1, y2]);
    events.push([x2, -1, y1, y2]);
  }
  events.sort((a, b) => a[0] - b[0]);
  const active = [];
  let prev = events[0][0];
  let area = 0n;
  const covered = () => {
    const sorted = [...active].sort((a, b) => a[0] - b[0]);
    let cov = 0, cur = -Infinity;
    for (const [a, b] of sorted) { cur = Math.max(cur, a); cov += Math.max(0, b - cur); cur = Math.max(cur, b); }
    return BigInt(cov);
  };
  for (const [x, sig, y1, y2] of events) {
    area = (area + covered() * BigInt(x - prev)) % MOD;
    if (sig === 1) active.push([y1, y2]);
    else active.splice(active.findIndex(p => p[0] === y1 && p[1] === y2), 1);
    prev = x;
  }
  return Number(area);
}

import java.util.*;
class Solution {
  public int rectangleArea(int[][] rectangles) {
    int MOD = 1_000_000_007;
    List<int[]> events = new ArrayList<>();
    for (int[] r : rectangles) {
      events.add(new int[]{r[0], 1, r[1], r[3]});
      events.add(new int[]{r[2], -1, r[1], r[3]});
    }
    events.sort((a, b) -> a[0] - b[0]);
    List<int[]> active = new ArrayList<>();
    int prev = events.get(0)[0];
    long area = 0;
    for (int[] e : events) {
      int x = e[0];
      long cov = covered(active);
      area = (area + cov * (x - prev)) % MOD;
      if (e[1] == 1) active.add(new int[]{e[2], e[3]});
      else active.removeIf(p -> p[0] == e[2] && p[1] == e[3]);
      prev = x;
    }
    return (int) (area % MOD);
  }
  long covered(List<int[]> active) {
    active.sort((a, b) -> a[0] - b[0]);
    long cov = 0; int cur = Integer.MIN_VALUE;
    for (int[] p : active) { cur = Math.max(cur, p[0]); cov += Math.max(0, p[1] - cur); cur = Math.max(cur, p[1]); }
    return cov;
  }
}

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int rectangleArea(vector<vector<int>>& rectangles) {
        const int MOD = 1e9 + 7;
        vector<tuple<int,int,int,int>> events;
        for (auto &r : rectangles) {
            events.emplace_back(r[0], 1, r[1], r[3]);
            events.emplace_back(r[2], -1, r[1], r[3]);
        }
        sort(events.begin(), events.end());
        vector<pair<int,int>> active;
        int prev = get<0>(events[0]);
        long long area = 0;
        auto covered = [&]() {
            auto sorted_act = active;
            sort(sorted_act.begin(), sorted_act.end());
            long long cov = 0; int cur = INT_MIN;
            for (auto &p : sorted_act) { cur = max(cur, p.first); cov += max(0, p.second - cur); cur = max(cur, p.second); }
            return cov;
        };
        for (auto &[x, sig, y1, y2] : events) {
            area = (area + covered() * (x - prev)) % MOD;
            if (sig == 1) active.emplace_back(y1, y2);
            else active.erase(find(active.begin(), active.end(), make_pair(y1, y2)));
            prev = x;
        }
        return area % MOD;
    }
};

Explanation

We need the total area covered by overlapping rectangles, counting any shared region only once. The trick is a vertical sweep line that moves left to right across the x-axis, measuring how much height is covered at each step.

Every rectangle becomes two events: a +1 event at its left edge x1 (the rectangle becomes active) and a -1 event at its right edge x2 (it turns off). We carry the rectangle's y-range with each event and sort all events by x.

Between two consecutive event x-positions, the set of active rectangles does not change, so the shape is a vertical strip. We compute the covered y-height with covered(), which merges the active y-intervals so overlaps are not double-counted, then add covered() * (x - prev_x) to the running area.

Example: with [[0,0,2,2],[1,0,2,3],[1,0,3,1]] the sweep adds up the strips of area as rectangles open and close. The merged y-coverage in each strip times its width sums to 6.

Because the active y-intervals are merged before measuring, regions shared by several rectangles count once, giving the true union area, taken modulo 10^9 + 7 at the end.

Time: O(n^2 log n) Space: O(n)