850. Rectangle Area II Hard

1/**
2 * [850] Rectangle Area II
3 *
4 * You are given a 2D array of axis-aligned rectangles. Each rectangle[i] = [xi1, yi1, xi2, yi2] denotes the i^th rectangle where (xi1, yi1) are the coordinates of the bottom-left corner, and (xi2, yi2) are the coordinates of the top-right corner.
5 * Calculate the total area covered by all rectangles in the plane. Any area covered by two or more rectangles should only be counted once.
6 * Return the total area. Since the answer may be too large, return it modulo 10^9 + 7.
7 *  
8 * Example 1:
9 * <img alt="" src="https://s3-lc-upload.s3.amazonaws.com/uploads/2018/06/06/rectangle_area_ii_pic.png" style="width: 600px; height: 450px;" />
10 * Input: rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
11 * Output: 6
12 * Explanation: A total area of 6 is covered by all three rectangles, as illustrated in the picture.
13 * From (1,1) to (2,2), the green and red rectangles overlap.
14 * From (1,0) to (2,3), all three rectangles overlap.
15 * 
16 * Example 2:
17 * 
18 * Input: rectangles = [[0,0,1000000000,1000000000]]
19 * Output: 49
20 * Explanation: The answer is 10^18 modulo (10^9 + 7), which is 49.
21 * 
22 *  
23 * Constraints:
24 * 
25 * 	1 <= rectangles.length <= 200
26 * 	rectanges[i].length == 4
27 * 	0 <= xi1, yi1, xi2, yi2 <= 10^9
28 * 
29 */
30pub struct Solution {}
31
32// problem: https://leetcode.com/problems/rectangle-area-ii/
33// discuss: https://leetcode.com/problems/rectangle-area-ii/discuss/?currentPage=1&orderBy=most_votes&query=
34
35// submission codes start here
36
37impl Solution {
38    pub fn rectangle_area(rectangles: Vec<Vec<i32>>) -> i32 {
39        0
40    }
41}
42
43// submission codes end
44
45#[cfg(test)]
46mod tests {
47    use super::*;
48
49    #[test]
50    fn test_850() {
51    }
52}
53