"""
tc O(N^2) sc O(N)
step1 :get unique x, sorted
step2:record idx of each x position, initialize cnt for tracking overlaps in at [x[i],x[i+1]]
step3: sort by y , use +1,-1 as mark to check if exist overlaps
area S = (cur_y - prev_y) * cur_x_sum
"""
class Solution:
def rectangleArea(self, rectangles: List[List[int]]) -> int:
mod = 10**9+7
X = sorted(set([x for x1,y1,x2,y2 in rectangles for x in [x1,x2]]))
x_i = {x:i for i,x in enumerate(X)}
cnt = [0] * len(X)
h = []
for x1,y1,x2,y2 in rectangles:
h.append([y1,x1,x2,1])
h.append([y2,x1,x2,-1])
h.sort()
# area S = (cur_y - prev_y) * cur_x_sum
S,prev_y,cur_x_sum = 0,0,0
for y,x1,x2,sign in h:
S += (y - prev_y) * cur_x_sum
prev_y = y
for i in range(x_i[x1],x_i[x2]):
# count[i] means the number of overlaps on the interval [x[i], x[i + 1]]
cnt[i] += sign
cur_x_sum = sum(x2-x1 if c else 0 for x1,x2,c in zip(X,X[1:],cnt))
return S % mod