The "Rectangle Area II" problem asks you to compute the total area covered by a list of axis-aligned rectangles on a 2D plane. Each rectangle is described by a list of four integers: [x1, y1, x2, y2], representing the coordinates of its bottom-left corner (x1, y1) and top-right corner (x2, y2). Rectangles may overlap, and the total area should count each region only once—overlapping regions should not be double-counted.
rectangles where each element is a rectangle as described above.10^9 + 7.Key Constraints:
[0, 10^9]At first glance, you might think of simply summing up the area of each rectangle. However, this approach fails when rectangles overlap, as regions in the overlap would be counted multiple times. To solve this, you need a way to "merge" the rectangles and ensure overlapping areas are only counted once.
The brute-force way would be to mark every unit square covered by any rectangle, but this is infeasible due to the massive possible coordinate range. Instead, we need a smarter approach—one that efficiently computes the union of all rectangles' areas without explicitly checking every point.
This leads us to the sweep line algorithm, a classic computational geometry technique. The idea is to "sweep" a line (usually vertical) across the plane, processing rectangle edges as events, and keeping track of the active intervals to compute covered areas efficiently.
We'll use a vertical sweep line algorithm. Here's how it works step by step:
x1), and one for its right edge (x2).[y1, y2]).dx = x_next - x_current) to get the area for that slice.10^9 + 7.This approach is efficient because it only processes events at rectangle edges and only merges intervals when necessary, avoiding the need to examine every individual point in the plane.
Let's consider the following rectangles:
[0,0,2,2][1,0,2,3][1,0,3,1]This process ensures that overlapping regions are only counted once.
Brute-force Approach: O(W * H) where W and H are the width and height of the bounding box—clearly infeasible for large coordinates.
Optimized Sweep Line Approach:
N \log N), where N is the number of rectangles.K \log K), where K is the number of active intervals (at most 2N).N^2 \log N) in the worst case, but much faster in practice with small N (N ≤ 200).N) for events and active interval lists.The Rectangle Area II problem requires careful handling of overlapping rectangles to avoid double-counting areas. By using a vertical sweep line algorithm and efficiently merging active y-intervals, we can compute the union area of all rectangles efficiently. This approach leverages event sorting and interval merging to handle overlaps seamlessly, providing an elegant and scalable solution to what at first seems like a daunting geometric challenge.
class Solution:
def rectangleArea(self, rectangles):
MOD = 10 ** 9 + 7
events = []
for x1, y1, x2, y2 in rectangles:
events.append((x1, 1, y1, y2)) # entering
events.append((x2, -1, y1, y2)) # leaving
events.sort()
import bisect
def merge(intervals):
intervals.sort()
merged = []
for start, end in intervals:
if not merged or merged[-1][1] <= start:
merged.append([start, end])
else:
merged[-1][1] = max(merged[-1][1], end)
return merged
cur_y_intervals = []
prev_x = events[0][0]
area = 0
for x, typ, y1, y2 in events:
# Calculate covered y-length
merged = merge(cur_y_intervals)
y_covered = 0
for s, e in merged:
y_covered += e - s
area += y_covered * (x - prev_x)
area %= MOD
if typ == 1:
cur_y_intervals.append([y1, y2])
else:
cur_y_intervals.remove([y1, y2])
prev_x = x
return area
class Solution {
public:
int rectangleArea(vector>& 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]); // entering
events.emplace_back(r[2], -1, r[1], r[3]); // leaving
}
sort(events.begin(), events.end());
vector<pair<int,int>> cur;
int prev_x = get<0>(events[0]);
long area = 0;
for (auto& [x, typ, y1, y2] : events) {
// Merge intervals
vector<pair<int,int>> merged;
sort(cur.begin(), cur.end());
for (auto& [s, e] : cur) {
if (merged.empty() || merged.back().second <= s) {
merged.push_back({s, e});
} else {
merged.back().second = max(merged.back().second, e);
}
}
long y_covered = 0;
for (auto& [s, e] : merged) y_covered += (e - s);
area = (area + y_covered * (x - prev_x)) % MOD;
if (typ == 1) {
cur.push_back({y1, y2});
} else {
for (auto it = cur.begin(); it != cur.end(); ++it) {
if (it->first == y1 && it->second == y2) {
cur.erase(it);
break;
}
}
}
prev_x = x;
}
return (int)area;
}
};
class Solution {
private static final int MOD = 1_000_000_007;
public int rectangleArea(int[][] rectangles) {
List<int[]> events = new ArrayList<>();
for (int[] r : rectangles) {
events.add(new int[]{r[0], 1, r[1], r[3]}); // entering
events.add(new int[]{r[2], -1, r[1], r[3]}); // leaving
}
events.sort((a, b) -> Integer.compare(a[0], b[0]));
List<int[]> cur = new ArrayList<>();
int prevX = events.get(0)[0];
long area = 0;
for (int[] event : events) {
int x = event[0], typ = event[1], y1 = event[2], y2 = event[3];
// Merge intervals
List<int[]> merged = new ArrayList<>();
cur.sort((a, b) -> Integer.compare(a[0], b[0]));
for (int[] interval : cur) {
if (merged.isEmpty() || merged.get(merged.size()-1)[1] <= interval[0]) {
merged.add(new int[]{interval[0], interval[1]});
} else {
merged.get(merged.size()-1)[1] = Math.max(merged.get(merged.size()-1)[1], interval[1]);
}
}
long y_covered = 0;
for (int[] m : merged) y_covered += m[1] - m[0];
area = (area + y_covered * (x - prevX)) % MOD;
if (typ == 1) {
cur.add(new int[]{y1, y2});
} else {
for (int i = 0; i < cur.size(); ++i) {
if (cur.get(i)[0] == y1 && cur.get(i)[1] == y2) {
cur.remove(i);
break;
}
}
}
prevX = x;
}
return (int)area;
}
}
var rectangleArea = function(rectangles) {
const MOD = 1e9 + 7;
let events = [];
for (let [x1, y1, x2, y2] of rectangles) {
events.push([x1, 1, y1, y2]); // entering
events.push([x2, -1, y1, y2]); // leaving
}
events.sort((a, b) => a[0] - b[0]);
let cur = [];
let prevX = events[0][0];
let area = 0;
function merge(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
let merged = [];
for (let [s, e] of intervals) {
if (!merged.length || merged[merged.length-1][1] <= s) {
merged.push([s, e]);
} else {
merged[merged.length-1][1] = Math.max(merged[merged.length-1][1], e);
}
}
return merged;
}
for (let [x, typ, y1, y2] of events) {
let merged = merge(cur);
let y_covered = 0;
for (let [s, e] of merged) y_covered += e - s;
area = (area + y_covered * (x - prevX)) % MOD;
if (typ === 1) {
cur.push([y1, y2]);
} else {
for (let i = 0; i < cur.length; ++i) {
if (cur[i][0] === y1 && cur[i][1] === y2) {
cur.splice(i, 1);
break;
}
}
}
prevX = x;
}
return area;
};