难度: 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 - 时间复杂度: O(N^2lgN)- 空间复杂度: O(N)******
参考Java TreeMap solution inspired by Skyline and Meeting Room
本来时间复杂度是O(N^2)，但是由于Python里面没有TreeMap，自己写了一下toTreeMap函数，时间变成O(N^2lgN)
cal_y函数最难理解
class Solution:
def rectangleArea(self, rectangles: 'List[List[int]]') -> 'int':
M = 10**9 + 7
points = []
for r in rectangles:
points.append((r[0], r[1], 1))
points.append((r[0], r[3], -1))
points.append((r[2], r[1], -1))
points.append((r[2], r[3], 1))
points.sort(key = lambda p: (p[0], -p[1]))
# print(points)
lookup = {}
prex, prey, res = -1, -1, 0
for i in range(len(points)):
p = points[i]
lookup[p[1]] = lookup.get(p[1], 0) + p[2]
lookup = self.toTreeMap(lookup)
# print(p)
# print(lookup)
if i == len(points) - 1 or points[i+1][0] > p[0]:
if prex > -1:
res += (prey * (p[0] - prex)) % M
res %= M
prey = self.cal_y(lookup)
# print(prey)
prex = p[0]
return res
def cal_y(self, maps):
res, pre, cnt = 0, -1, 0
for k, v in maps.items():
if cnt > 0:
res += k - pre
cnt += v
pre = k
return res
def toTreeMap(self, maps):
treemap = collections.OrderedDict()
for key in sorted(maps.keys()):
treemap[key] = maps.get(key)
return treemap思路 2 - 时间复杂度: O(N^2)- 空间复杂度: O(N)******
参考[C++/Python] Discretization and O(NlogN)
solution来自yidong_w
个人认为他的solution更容易理解一些
I found your code is a little difficult for me to understand,
so I took your idea and wrote a similar solution.
It is scanning level by level. It will add to the result once it reach to the next level.
Any sub rectangles that has count > 0 will be counted as valid rectangle.
from heapq import heappush, heappop
class Solution:
def rectangleArea(self, rectangles: 'List[List[int]]') -> 'int':
x, pq = set(), []
for rec in rectangles:
x.add(rec[0])
x.add(rec[2])
heappush(pq, (rec[1], rec[0], rec[2], 1))
heappush(pq, (rec[3], rec[0], rec[2], -1))
x = sorted(list(x))
xi = {v:i for i,v in enumerate(x)}
count = [0] * len(x)
# print(pq)
# print(x)
# print(xi)
res = 0
last_y = cur_y = pq[0][0]
while pq:
cur_y = pq[0][0]
for i in range(len(x)):
if count[i] > 0:
# print('x: ', i)
res += (x[i+1] - x[i]) * (cur_y - last_y)
res %= (10**9 + 7)
# print(res)
while pq and pq[0][0] == cur_y:
cur_y, x1, x2, bound = heappop(pq)
# 这里右边界蛮关键的，最后一个i的count不用加上bound，这与第29行的x[i+1]有关，否则会out of bound
for i in range(xi[x1], xi[x2]):
count[i] += bound
last_y = cur_y
# print(count)
return res思路 3 - 时间复杂度: O(N^2)- 空间复杂度: O(N^2)******
此题的思路是，将题目所给的所有矩形的坐标点都集中起来组成一个网格。具体来说，将所有的X坐标集中起来（要去除重复），将所有的Y坐标集中起来，然后将其两两配对组成一个二维的网络。注意，这样的网格点之间的实际距离并不是均匀的，但是没有关系。
我们再来遍历所有的矩形：在这个网络中找到每个矩形所框起来的范围（遵循左闭右开的原则），标记这个范围内的网格点为true，意味着这些网格点是落在被cover的面积里。遍历完所有的矩形后，所有标记为true的网格点都是要被算入面积的，而那些没有标记的说明不用被计算。
可以知道，凡是被cover的网格点(u,v)，它所代表的面积就是(x[u+1]-x[u])*(y[v+1]-y[v])。我们只需要累加这些网格点所代表的面积即可。
这个思路是我觉得很好的一个
class Solution:
def rectangleArea(self, rectangles: 'List[List[int]]') -> 'int':
setx, sety = set(), set()
for rec in rectangles:
setx.add(rec[0])
setx.add(rec[2])
sety.add(rec[1])
sety.add(rec[3])
x, y = sorted(list(setx)), sorted(list(sety))
m, n = len(x), len(y)
points = [[0] * n for _ in range(m)]
for rec in rectangles:
x0 = bisect.bisect_left(x, rec[0])
x1 = bisect.bisect_left(x, rec[2])
y0 = bisect.bisect_left(y, rec[1])
y1 = bisect.bisect_left(y, rec[3])
for i in range(x0, x1):
for j in range(y0, y1):
points[i][j] = 1
res, mod = 0, 10 ** 9 + 7
for i in range(m-1):
for j in range(n-1):
if points[i][j] == 0:
continue
res += (x[i+1] - x[i]) * (y[j+1] - y[j])
res %= mod
return res