Description
Suppose that there are N rectangles. Each side of the rectangle is parallel to the x-axis and the y-axis. Each rectangle has the left bottom coordinate (x1, y1) and the right top coordinate (x2, y2), which is represented as (x1, y1, x2, y2). Each rectangle can be overlapped with each other. You want to know the size occupied by the rectangles. The following is an example when N=5.
In the above figure, 5 rectangles (1, 1, 6, 5), (2, 0, 4, 2), (2, 4, 5, 7), (4, 3, 8, 6), (7, 5, 9, 7) are placed. The size covered by all the rectangles is the same size within the black border.
In the above example, the size covered by the 5 rectangles is 38.
Given the coordinates of rectangles on the plane rectangles
as a parameter, write a function solution
to return the size covered by the rectangles.
Constraints
- The number of rectangles N : 1 ≤ N ≤ 100,000
- The coordinates or rectangles : x1, y1, x2, y2 : 0 ≤ x1 < x2 ≤ 109 , 0 ≤ y1 < y2 ≤ 109
- x1, y1, x2, y2 are integer number.
Examples
rectangles | result |
---|---|
[[0, 1, 4, 4], [3, 1, 5, 3]] | 14 |
[[1, 1, 6, 5], [2, 0, 4, 2], [2, 4, 5, 7], [4, 3, 8, 6], [7, 5, 9, 7]] | 38 |
Example #1
The size occupied by the rectangle (0, 1, 4, 4) and (3, 1, 5, 3) are 12 and 4, respectively. Since the size overlapped by 2 rectangles is 2, total size is 12 + 4 - 2 = 14.
Example #2
This is the same with an example in problem statement.