Leetcode 850. Rectangle Area II
Problem Explanation
The problem requires finding the total area covered by all rectangles whose coordinates are given. The coordinates represent the bottom-left and the top-right corner of each rectangle. It is important to note that the rectangles could overlap, and in such cases, the overlapping area should not be counted twice. Return the answer modulo 10^9 + 7 because the area covered may be very large.
For example, given the following rectangles:[[0,0,2,2],[1,0,2,3],[1,0,3,1]], the total area covered is 6. This is because the first rectangle covers an area of 4, the second one covers an area of 3, and the third one covers an area of 2. However, since the second and the third rectangle overlap covering an area of 1 and the first and the second rectangle also overlap covering an area of 2, these overlapping areas should only be counted once. Thus the total area covered by all rectangles is 4+3+2-(1 + 2) =6.
Solution Approach
The solution uses a line sweep algorithm. The line sweep algorithm is a computational geometry algorithm that uses a conceptual sweep line that moves across the plane to solve various problems. Here, it is used to replicate drawing the rectangles from left to right.
Each rectangle adds two events - a "start" event when the most left side is first encountered and an "end" event when the most right side is hit. These events are sorted by their x-coordinate, forming a queue.
Then, the events are traversed. The area combined between each pair of events is calculated. If the event is a "start" event, its y1 and y2 are added to vector yPairs; if it is an "end" event, the pair y1 and y2 is removed from vector yPairs. The height of the overlapped area is calculated using function getHeight that iterates through yPairs. Finally, the total combined area is returned as the result.
Python Solution
1 2python 3class Solution: 4 def rectangleArea(self, rectangles): 5 # Create a list of boundaries and events 6 events = [] 7 for x1, y1, x2, y2 in rectangles: 8 # append start events and end events 9 events.append((x1, y1, y2, 1)) 10 events.append((x2, y1, y2, -1)) 11 # Sort the events by x coordinate 12 events.sort() 13 14 # Define a function to calculate covered y range 15 def calcY(): 16 # If there is no active y range, return 0 17 if not active: return 0 18 # Calculate the covered y range 19 return active[-1][1] - active[0][0] 20 21 area = 0 22 active = [] 23 cur_x = events[0][0] 24 for x, y1, y2, t in events: 25 # Calculate the area covered since last x coordinate 26 area += calcY() * (x - cur_x) 27 area %= 10**9 + 7 28 29 # update cur_x 30 cur_x = x 31 32 # Update active intervals 33 i = bisect.bisect_left(active, (y1, float('inf'))) 34 j = bisect.bisect_left(active, (y2, float('inf'))) 35 # If it is start event, add a new active y range 36 # If it is end event, remove the active y range 37 active[i:j] = [] if t == -1 else [(y1, y2)] 38 39 return area
Java Solution
1
2java
3public class Solution {
4 public int rectangleArea(int[][] rectangles) {
5 int N = rectangles.length;
6 Event[] events = new Event[N*2];
7 int t = 0;
8 for (int[] rec: rectangles) {
9 events[t++] = new Event(rec[1], rec[0], rec[2], true);
10 events[t++] = new Event(rec[3], rec[0], rec[2], false);
11 }
12
13 Arrays.sort(events, new Comparator<Event>() {
14 public int compare(Event a, Event b) {
15 if (a.time != b.time) return a.time - b.time;
16 return a.isStart ? -1 : 1;
17 }
18 });
19
20 List<Interval> active = new ArrayList();
21 long ans = 0;
22 long cur_y = events[0].time;
23 for (Event event: events) {
24 long y = event.time;
25 if (y > cur_y) {
26 ans += calculateInterval(active) * (y - cur_y);
27 ans %= 1_000_000_007;
28 cur_y = y;
29 }
30
31 int idx = Collections.binarySearch(active, new Interval(event.start, event.end));
32 if (event.isStart) {
33 if (idx < 0) idx = ~idx;
34 active.add(idx, new Interval(event.start, event.end));
35 } else {
36 active.remove(idx);
37 }
38 }
39
40 return (int) ans;
41 }
42
43 public long calculateInterval(List<Interval> intervals) {
44 int N = intervals.size();
45 long ans = 0, cur = -1;
46 for (Interval interval: intervals) {
47 cur = Math.max(cur, interval.start);
48 ans += Math.max(interval.end - cur, 0);
49 cur = Math.max(cur, interval.end);
50 }
51 return ans;
52 }
53
54 class Interval implements Comparable<Interval> {
55 int start, end;
56 Interval(int start, int end) {
57 this.start = start;
58 this.end = end;
59 }
60
61 public int compareTo(Interval that) {
62 if (this.start != that.start) return this.start - that.start;
63 else return this.end - that.end;
64 }
65 }
66
67 class Event {
68 int time, start, end;
69 boolean isStart;
70 Event(int t, int s, int e, boolean isS) {
71 time = t;
72 start = s;
73 end = e;
74 isStart = isS;
75 }
76 }
77}
C++ Solution
1 2cpp 3class Solution { 4public: 5 int rectangleArea(vector<vector<int>>& rectangles) { 6 int mod = pow(10, 9) + 7; 7 vector<pair<int, pair<int, int>>> vp; 8 for(auto r : rectangles) 9 { 10 vp.push_back({r[0], {r[1], -r[3]}}); 11 vp.push_back({r[2], {r[1], r[3]}}); 12 } 13 sort(vp.begin(), vp.end()); 14 multiset<pair<int, int>> ms; 15 long area = 0, length = 0; 16 for(int i = 0; i < vp.size(); i++) 17 { 18 if(i > 0) 19 area = (area + ((vp[i].first - vp[i - 1].first) * length)) % mod; 20 if(vp[i].second.second < 0) 21 ms.insert({vp[i].second.first, -vp[i].second.second}); 22 else 23 { 24 ms.erase(ms.find({vp[i].second.first, vp[i].second.second})); 25 } 26 length = 0; 27 if(!ms.empty()) 28 { 29 auto it = ms.begin(); 30 int start = it -> first, end = it -> second; 31 while(it != ms.end()) 32 { 33 start = max(start, it -> first); 34 end = max(end, it -> second); 35 if(it -> first > end) 36 { 37 length += end - start; 38 start = it -> first; 39 end = it -> second; 40 } 41 it++; 42 } 43 length += end - start; 44 } 45 } 46 return area; 47 } 48};
C# Solution
1 2csharp 3public class Solution { 4 public int RectangleArea(int[][] rectangles) { 5 int mod = (int)Math.Pow(10, 9) + 7; 6 var list = new List<double[]>(); 7 foreach (var rec in rectangles) { 8 list.Add(new double[] { rec[1], rec[0], rec[2], 1 }); // Add start event 9 list.Add(new double[] { rec[3], rec[0], rec[2], - 1 }); // Add end event 10 } 11 // Sort the list by y-axis 12 list.Sort((a, b) => (a[0] != b[0] ? a[0].CompareTo(b[0]) : a[3] * a[1] - b[3] * b[1])); 13 var active = new List<int[]>(); 14 int n = rectangles.Length, cur = 0; 15 long res = 0, width = 0; 16 foreach (var l in list) { 17 int y = (int)l[0], left = (int)l[1], right = (int)l[2], sig = (int)l[3]; 18 res = (long)((res + width * (y - cur)) % mod); 19 cur = y; // Update the current position to y 20 if (sig == 1) active.Add(new int[] { left, right }); // If it is start event, add to list 21 else active.RemoveAll(a => a[0] == left && a[1] == right); // If it is close event, remove from list 22 active.Sort((a, b) => a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]); // Sort the active list 23 width = 0; // Reset width to 0 24 int cur_left = -1, cur_right = -1; // Set current left and right to -1 25 foreach (var a in active) { // Traverse the active list to consolidate width 26 cur_left = Math.Max(cur_left, a[0]); 27 cur_right = Math.Max(cur_right, a[1]); 28 if (cur_left >= cur_right) { 29 width += cur_right - a[0]; 30 cur_left = a[0]; 31 cur_right = a[1]; 32 } 33 } 34 } 35 return (int)res; 36 } 37}
JavaScript Solution
1 2javascript 3const rectangleArea = function(rectangles) { 4 const MOD = 10**9 + 7; 5 6 let events = []; 7 for (let [x1, y1, x2, y2] of rectangles) { 8 events.push([y1, x1, x2, 1]); 9 events.push([y2, x1, x2, -1]); 10 } 11 12 // Sort the events 13 events.sort((a, b) => a[0] - b[0]); 14 15 let active = new Map(); 16 let area = 0; 17 let cur_y = events[0][0]; 18 19 // Go through each event 20 for (let [y, x1, x2, sig] of events) { 21 // For the y-range between the current event and the last event, increase the answer by the sum of widths 22 let sum = 0, cur = -1; 23 24 for (let [x, count] of active) { 25 if (cur >= 0 && count > 0) sum += x - cur; 26 cur = x; 27 } 28 29 area += sum * (y - cur_y); 30 area %= MOD; 31 32 cur_y = y; 33 34 // Update active intervals 35 let count = active.get(x1) || 0; 36 if (count + sig > 0) active.set(x1, count + sig); 37 else active.delete(x1); 38 39 count = active.get(x2) || 0; 40 if (count - sig > 0) active.set(x2, count - sig); 41 else active.delete(x2); 42 } 43 44 return area; 45};
The different code snippets outlined above illustrate how to solve the problem using different programming languages, such as Python, Java, JavaScript, C++, and C#.
The takeaways from these solutions are:
-
The line sweep algorithm is applied across all the languages. This algorithm is a computational geometry algorithm for efficiently solving problems on the plane.
-
In all solutions, the coordinates of the corners of the rectangles are turned into events. These events are sorted based on their x-coordinates. This way, the algorithm can ensure that the events are processed in the correct order.
-
The vertices are processed one by one. If a vertex is on the left edge of a rectangle, the rectangle's vertical line segment is added to the line sweep state. If a vertex is on the right edge of a rectangle, its line segment is removed from the state.
-
The line sweep algorithm requires understanding and manipulation of data structures. In the Python solution, they use a sorted list of pairs to represent the active y-ranges. Java uses an ArrayList to maintain the active y-ranges, whereas C# and JavaScript use a Map to represent the same.
-
In the Java, C++, and C# solutions, a helper function is used to calculate the width covered by the active intervals.
-
In the JavaScript solution, they use a Map to represent active x-ranges. This allows for easier addition and removal of active x-ranges.
-
The final area is calculated by multiplying the sum of widths of the current active x-ranges with the difference in y-values between the current and the previous event. This area is accumulated and returned as the answer, with the modulo operation applied to prevent overflow.
Each of these solutions offers a different perspective on how to apply the line sweep algorithm to solve this problem. The key is understanding how the algorithm works and how to effectively use data structures to assist in the computation.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.