Tuesday, September 22, 2020

LeetCode [850] Rectangle Area II

 850. Rectangle Area II

Hard

We are given a list of (axis-aligned) rectangles.  Each rectangle[i] = [x1, y1, x2, y2] , where (x1, y1) are the coordinates of the bottom-left corner, and (x2, y2) are the coordinates of the top-right corner of the ith rectangle.

Find the total area covered by all rectangles in the plane.  Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
Output: 6
Explanation: As illustrated in the picture.

Example 2:

Input: [[0,0,1000000000,1000000000]]
Output: 49
Explanation: The answer is 10^18 modulo (10^9 + 7), which is (10^9)^2 = (-7)^2 = 49.

Note:

  • 1 <= rectangles.length <= 200
  • rectanges[i].length = 4
  • 0 <= rectangles[i][j] <= 10^9
  • The total area covered by all rectangles will never exceed 2^63 - 1 and thus will fit in a 64-bit signed integer.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
    public int rectangleArea(int[][] rectangles) {
        int OPEN = 0, CLOSE = 1;
        int[][] events = new int[2*rectangles.length][4];
        
        int t = 0;
        for(int[] rect : rectangles) {
            events[t++] = new int[]{rect[1], OPEN, rect[0], rect[2]};
            events[t++] = new int[]{rect[3], CLOSE, rect[0], rect[2]};
        }
        
        List<int[]> active = new ArrayList();
        Arrays.sort(events, (e1, e2) -> {
            return Integer.compare(e1[0], e2[0]);
        });
        
        long ans = 0;
        int currY = events[0][0]; 
        for(int[] event : events) {
            int y = event[0];
            int state = event[1];
            int x1 = event[2];
            int x2 = event[3];
            
            long query = 0;
            int curr = -1;
            for(int[] activeEvent : active) {
                curr = Math.max(curr, activeEvent[0]);
                query += Math.max(activeEvent[1] - curr, 0);
                curr = Math.max(curr, activeEvent[1]);
            }
            
            ans += query*(y - currY);
            
            if(state == OPEN) {
                active.add(new int[]{x1, x2});
                Collections.sort(active, (i1, i2) -> {
                    return Integer.compare(i1[0], i2[0]);
                });
            } else {
                for(int i=0; i<active.size(); i++) {
                    if (active.get(i)[0] == x1 && active.get(i)[1] == x2) {
                        active.remove(i);
                        break;
                    }
                }
            }
            currY = y;
        }
        
        ans %= 1_000_000_007;
        return (int)ans;
    }
}
at

No comments:

Post a Comment