Sponsored
Sponsored
This approach involves treating rectangle edges as events (start and end), which we can sort and process sequentially. By sweeping across the x-axis and using a data structure, like Segment Tree or Balance Tree, to merge y-intervals, we can efficiently calculate the union area of rectangles.
Time Complexity: O(N^2 log N), where N is the number of rectangles. Sorting events takes O(N log N), and updating y-interval intervals can be up to O(N) operations for each event.
Space Complexity: O(N) for storing events and active intervals structures.
1def rectangleArea(rectangles):
2 MOD = 10**9 + 7
3 OPEN, CLOSE = 1, -1
4 events = []
5 for x1, y1, x2, y2 in rectangles:
6 events.append((x1, OPEN, y1, y2))
7 events.append((x2, CLOSE, y1, y2))
8 events.sort()
9
10 def add(intervals, y1, y2):
11 added_intervals = []
12 new_interval = [y1, y2]
13 for i, (a, b) in enumerate(intervals):
14 if b < y1 or y2 < a:
15 added_intervals.append([a, b])
16 else:
17 new_interval = [min(a, new_interval[0]), max(b, new_interval[1])]
18 added_intervals.append(new_interval)
19 return added_intervals
20
21 def measure(intervals):
22 return sum(y2 - y1 for y1, y2 in intervals)
23
24 curr_y_intervals = []
25 last_x = events[0][0]
26 area = 0
27
28 for x, typ, y1, y2 in events:
29 area += measure(curr_y_intervals) * (x - last_x)
30 if typ == OPEN:
31 curr_y_intervals = add(curr_y_intervals, y1, y2)
32 else:
33 curr_y_intervals.remove([y1, y2])
34 curr_y_intervals.sort()
35 last_x = x
36
37 return area % MODThe solution uses a line sweep algorithm where rectangles are decomposed into events indicating if a horizontal segment is starting or ending. These events are sorted by the x-coordinate and processed to update the active intervals on the y-axis. A helper function manages merging y-intervals actively covered, calculating the cumulative area exposed over the previous segment width.
This approach involves using the inclusion-exclusion principle to calculate the area by adding all single rectangle areas and subtracting all pairwise overlaps calculated recursively. The approach is computationally intensive for the direct calculation but less error-prone for conceptual integrity.
Time Complexity: O(N log N), where the log component comes from interval set operations inherent in TreeMap.
Space Complexity: O(N), mainly for storing events and active structures.
1import java.util.*;
2
3public class RectangleAreaII
This approach uses the scanline technique combined with a segment tree to handle the union of rectangles. The scanline approach will treat each x-coordinate boundary as an event, i.e., where a rectangle starts or ends. These events allow efficient checking with a segment tree, which tracks active y-intervals.
Time complexity: O(N log N), where N is the number of events. This arises from sorting the events and using a segment tree for dynamic interval management.
Space complexity: O(N), for storing sorted y-coordinates and constructing the segment tree.
1class SegmentTree:
2 def __init__
In this approach, we handle the vertical lines or events by consolidating intervals along the x-direction using coordinate compression. The active intervals along the y-axis are populated dynamically as the events are processed. Unlike a Segment Tree, this approach uses a simpler interval tracking to combine overlapping y-segments.
Time complexity: O(N log N), given the sorting of events and y-coordinates.
Space complexity: O(N), for event storage and y-indices tracking.
1import java.util.ArrayList;
2
This Java implementation uses a TreeMap to keep track of active y-intervals, adding or removing intervals based on the type of event being processed. The expansion of the x-coordinate determines how much additional area to count between events. The TreeMap simplifies the merging and tracking of overlapping y-intervals.
We define a Segment Tree to manage y-coordinates, offering efficient updates for overlapping segments and interval covering. We iterate over event points in sorted order, updating the segment tree for each x-coordinate while calculating the area contribution to the result. Using modulo operation keeps the result scaled within bounds.
This approach defines events across x-coordinates, adjusting interval coverage along the y-axis using count to handle rectangle entry and exits succinctly. By employing coordinate compression and a simple interval logic, it systematically accumulates the total covered area.