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.

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Sweep line algorithms

Range queries

Segment trees revisited

Starter code: class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        

Solutions:
class Solution:

	def rectangleArea(self, rectangles: List[List[int]]) -> int:

		def getArea(width):
			res = 0
			prev_low = 0
			for (low, high) in intervals:
				low = max(prev_low, low)
				if high > low:
					res += (high - low) * width
					prev_low = high
			return res
		MOD = 10 ** 9 + 7
		events = []
		for (x1, y1, x2, y2) in rectangles:
			events.append((x1, 0, y1, y2))
			events.append((x2, 1, y1, y2))
		events.sort(key=lambda x: (x[0], x[1]))
		intervals = []
		area = 0
		prev_x = 0
		for event in events:
			(cur_x, type, low, high) = event
			area += getArea(cur_x - prev_x)
			if type == 1:
				intervals.remove((low, high))
			else:
				intervals.append((low, high))
				intervals.sort()
			prev_x = cur_x
		return area % MOD


class Solution:

	def rectangleArea(self, rectangles: List[List[int]]) -> int:
		mod = 10 ** 9 + 7
		events = []
		for (x1, y1, x2, y2) in rectangles:
			events.append([x1, 0, y1, y2])
			events.append([x2, 1, y1, y2])
		events.sort(key=lambda x: (x[0], -x[1]))

		def getArea(m):
			area = 0
			prev = float('-inf')
			for (l, r) in heights:
				prev = max(prev, l)
				area += max(0, r - prev) * m
				prev = max(prev, r)
			return area
		area = 0
		prev = 0
		heights = []
		for event in events:
			(cur, close, y1, y2) = event
			area += getArea(cur - prev)
			if close:
				heights.remove((y1, y2))
			else:
				heights.append((y1, y2))
				heights.sort()
			prev = cur
		return area % mod


class Solution:

	def rectangleArea(self, rectangles):
		(OPEN, CLOSE) = (1, -1)
		events = []
		nonlocal X
		X = set()
		for (x1, y1, x2, y2) in rectangles:
			events.append((y1, OPEN, x1, x2))
			events.append((y2, CLOSE, x1, x2))
			X.add(x1)
			X.add(x2)
		events.sort()
		X = sorted(X)
		Xi = {x: i for (i, x) in enumerate(X)}
		active = Node(0, len(X) - 1)
		ans = 0
		cur_x_sum = 0
		cur_y = events[0][0]
		for (y, typ, x1, x2) in events:
			ans += cur_x_sum * (y - cur_y)
			cur_x_sum = active.update(Xi[x1], Xi[x2], typ)
			cur_y = y
		return ans % (10 ** 9 + 7)

class Node(object):

	def __init__(self, start, end):
		(self.start, self.end) = (start, end)
		self.total = self.count = 0
		self._left = self._right = None

	@property
	def mid(self):
		return (self.start + self.end) // 2

	@property
	def left(self):
		self._left = self._left or Node(self.start, self.mid)
		return self._left

	@property
	def right(self):
		self._right = self._right or Node(self.mid, self.end)
		return self._right

	def update(self, i, j, val):
		if i >= j:
			return 0
		if self.start == i and self.end == j:
			self.count += val
		else:
			self.left.update(i, min(self.mid, j), val)
			self.right.update(max(self.mid, i), j, val)
		if self.count > 0:
			self.total = X[self.end] - X[self.start]
		else:
			self.total = self.left.total + self.right.total
		return self.total


class Solution:

	def rectangleArea(self, rectangles: List[List[int]]) -> int:
		Xs = [x for (x1, _, x2, _) in rectangles for x in [x1, x2]]
		Xs.sort()
		X_idx_lookup = {x: idx for (idx, x) in enumerate(Xs)}
		res = 0
		prev_y = 0
		X_span = 0
		Ys = [e for (x1, y1, x2, y2) in rectangles for e in [[y1, x1, x2, 1], [y2, x1, x2, -1]]]
		Ys.sort()
		overlap_count = [0] * len(Xs)
		for (y, xl, xr, inout) in Ys:
			res += (y - prev_y) * X_span
			prev_y = y
			(start_idx, end_idx) = (X_idx_lookup[xl], X_idx_lookup[xr])
			for i in range(start_idx, end_idx):
				overlap_count[i] += inout
			X_span = sum((x2 - x1 if c > 0 else 0 for (x1, x2, c) in zip(Xs, Xs[1:], overlap_count)))
		return res % 1000000007

	def rectangleArea(self, rectangles: List[List[int]]) -> int:
		Xs = [x for (x1, _, x2, _) in rectangles for x in [x1, x2]]
		Xs.sort()
		covered = [0] * len(Xs)
		res = 0
		keypoints = [e for (x1, y1, x2, y2) in rectangles for e in [[y1, x1, x2, 1], [y2, x1, x2, -1]]]
		keypoints.sort()
		prev_y = 0
		width_span = 0
		for (y, x1, x2, inout) in keypoints:
			res += (y - prev_y) * width_span
			prev_y = y
			for i in range(len(covered) - 1):
				(a, b) = (Xs[i], Xs[i + 1])
				if x1 <= a and b <= x2:
					covered[i] += inout
			width_span = sum((Xs[i + 1] - Xs[i] if covered[i] > 0 else 0 for i in range(len(covered) - 1)))
		return res % 1000000007


class Solution:

	def rectangleArea(self, rectangles: List[List[int]]) -> int:
		START = 1
		END = 0
		MOD = 10 ** 9 + 7
		xaxis = []
		for (x1, y1, x2, y2) in rectangles:
			xaxis.append((x1, START, y1, y2))
			xaxis.append((x2, END, y1, y2))
		xaxis.sort()
		prev = 0
		area = 0
		yaxis = []
		for i in range(len(xaxis)):
			(x, status, y1, y2) = xaxis[i]
			if i > 0:
				area += self.get_length(yaxis) * (x - prev)
				area %= MOD
			if status == START:
				yaxis.append((y1, y2))
				yaxis.sort()
			else:
				yaxis.remove((y1, y2))
			prev = x
		return area

	def get_length(self, yaxis):
		length = 0
		i = 0
		prev = (float('-inf'), float('-inf'))
		for i in range(len(yaxis)):
			if not self.has_overlap(prev, yaxis[i]):
				length += yaxis[i][1] - yaxis[i][0]
			else:
				if prev[1] >= yaxis[i][1]:
					continue
				length += yaxis[i][1] - prev[1]
			prev = yaxis[i]
		return length

	def has_overlap(self, prev, cur):
		if prev[1] < cur[0] or cur[1] < prev[0]:
			return False
		return True

	def get_overlap_length(self, prev, cur):
		return min(prev[1], cur[1]) - max(prev[0], cur[0])


class Tree:

	def __init__(self, l, r):
		self.total = 0
		self.count = 0
		self.l = l
		self.r = r
		self.m = int((self.l + self.r) / 2)
		self.isLeaf = True if self.r - self.l == 1 else False
		self.left = None if self.isLeaf else Tree(self.l, self.m)
		self.right = None if self.isLeaf else Tree(self.m, self.r)

	def update(self, l, r, count):
		if l >= self.r or r <= self.l:
			return
		if self.isLeaf:
			self.count += count
			self.total = nums[self.r] - nums[self.l] if self.count else 0
		else:
			self.left.update(l, r, count)
			self.right.update(l, r, count)
			self.total = self.left.total + self.right.total

class Solution(object):

	def rectangleArea(self, rectangles):
		M = 10 ** 9 + 7
		events = []
		nonlocal nums
		nums = set()
		for (x1, y1, x2, y2) in rectangles:
			events.append((x1, y1, y2, 1))
			events.append((x2, y1, y2, -1))
			nums.add(y1)
			nums.add(y2)
		nums = list(nums)
		nums.sort()
		nToI = dict([(n, i) for (i, n) in enumerate(nums)])
		iTree = Tree(0, len(nums) - 1)
		events.sort(key=lambda x: x[0])
		res = 0
		prev = events[0][0]
		for event in events:
			if event[0] != prev:
				res += iTree.total * (event[0] - prev)
				res = res % M
				prev = event[0]
			iTree.update(nToI[event[1]], nToI[event[2]], event[3])
		return res


class Solution:

	def rectangleArea(self, rectangles: List[List[int]]) -> int:
		rects = []
		for (x1, y1, x2, y2) in rectangles:
			self.helper(rects, 0, x1, y1, x2, y2)
		ans = 0
		mod = pow(10, 9) + 7
		for (x1, y1, x2, y2) in rects:
			ans += (x2 - x1) * (y2 - y1) % mod
		return ans % mod

	def helper(self, rects, index, x1, y1, x2, y2):
		if index == len(rects):
			rects.append([x1, y1, x2, y2])
			return
		(i1, j1, i2, j2) = rects[index]
		if i1 >= x2 or i2 <= x1 or j1 >= y2 or (j2 <= y1):
			self.helper(rects, index + 1, x1, y1, x2, y2)
			return
		if x1 < i1:
			self.helper(rects, index + 1, x1, y1, min(i1, x2), y2)
		if x2 > i2:
			self.helper(rects, index + 1, max(i2, x1), y1, x2, y2)
		if y1 < j1:
			self.helper(rects, index + 1, max(x1, i1), y1, min(x2, i2), j1)
		if y2 > j2:
			self.helper(rects, index + 1, max(x1, i1), j2, min(x2, i2), y2)


MOD = 10 ** 9 + 7

class Solution:

	def rectangleArea(self, rectangles: List[List[int]]) -> int:
		allY = []
		for (x1, y1, x2, y2) in rectangles:
			allY.append((y1, 0, x1, x2))
			allY.append((y2, 1, x1, x2))
		allY.sort()
		(allX, ans) = ([], 0)
		curHeight = allY[0][0]
		for (y, t, x1, x2) in allY:
			ans += self.getX(allX) * (y - curHeight)
			ans %= MOD
			if t == 0:
				bisect.insort(allX, (x1, x2))
			else:
				idx = bisect.bisect_left(allX, (x1, x2))
				allX.pop(idx)
			curHeight = y
		return ans

	def getX(self, allX):
		ans = 0
		cur = -1
		for (x1, x2) in allX:
			cur = max(cur, x1)
			ans += max(0, x2 - cur)
			cur = max(cur, x2)
		return ans


class Solution:

	def rectangleArea(self, rects: List[List[int]]) -> int:
		xs = sorted(set([x for (x1, y1, x2, y2) in rects for x in [x1, x2]]))
		xi = {v: i for (i, v) in enumerate(xs)}
		cnt = [0] * len(xs)
		L = []
		for (x1, y1, x2, y2) in rects:
			L.append([y1, x1, x2, 1])
			L.append([y2, x1, x2, -1])
		L.sort()
		res = last_y = sum_x = 0
		for (y, x1, x2, sig) in L:
			res += (y - last_y) * sum_x
			last_y = y
			for i in range(xi[x1], xi[x2]):
				cnt[i] += sig
			sum_x = sum((x2 - x1 for (x1, x2, c) in zip(xs, xs[1:], cnt) if c))
		return res % (10 ** 9 + 7)


class Solution:

	def rectangleArea(self, rectangles: List[List[int]]) -> int:
		xs = sorted(list(set((x for (x1, y1, x2, y2) in rectangles for x in [x1, x2]))))
		xs_i = {x: i for (i, x) in enumerate(xs)}
		rects = []
		for (x1, y1, x2, y2) in rectangles:
			rects.append((y1, x1, x2, 1))
			rects.append((y2, x1, x2, -1))
		rects = sorted(rects)
		counts = [0] * len(xs_i)
		curr_y = 0
		area = 0
		L = 0
		for (y, x1, x2, sig) in rects:
			area += (y - curr_y) * L
			curr_y = y
			for x in range(xs_i[x1], xs_i[x2]):
				counts[x] += sig
			L = sum((x2 - x1 for (x1, x2, s1) in zip(xs, xs[1:], counts) if s1 > 0))
		return area % (10 ** 9 + 7)


class Solution:

	def rectangleArea(self, rectangles: List[List[int]]) -> int:
		all_rectangles = []
		for rectangle in rectangles:
			self.add_rectangle(all_rectangles, rectangle, 0)
		ans = 0
		mod = pow(10, 9) + 7
		for rect in all_rectangles:
			(x1, y1, x2, y2) = rect
			ans += (x2 - x1) * (y2 - y1) % mod
		return ans % mod

	def add_rectangle(self, all_rectangles, cur, start):
		if start >= len(all_rectangles):
			all_rectangles.append(cur)
			return
		(x1, y1, x2, y2) = cur
		(rx1, ry1, rx2, ry2) = all_rectangles[start]
		if x2 <= rx1 or x1 >= rx2 or y2 <= ry1 or (y1 >= ry2):
			self.add_rectangle(all_rectangles, cur, start + 1)
			return
		if x1 < rx1:
			self.add_rectangle(all_rectangles, [x1, y1, rx1, y2], start + 1)
		if x2 > rx2:
			self.add_rectangle(all_rectangles, [rx2, y1, x2, y2], start + 1)
		if y1 < ry1:
			self.add_rectangle(all_rectangles, [max(x1, rx1), y1, min(x2, rx2), ry1], start + 1)
		if y2 > ry2:
			self.add_rectangle(all_rectangles, [max(x1, rx1), ry2, min(x2, rx2), y2], start + 1)


class Solution:

	def rectangleArea(self, rectangles: List[List[int]]) -> int:
		xTicks = set()
		yTicks = set()
		for (x1, y1, x2, y2) in rectangles:
			xTicks.add(x1)
			xTicks.add(x2)
			yTicks.add(y1)
			yTicks.add(y2)
		xTicksList = sorted(list(xTicks))
		yTicksList = sorted(list(yTicks))
		xTicksDict = {xLable: xi for (xi, xLable) in enumerate(xTicksList)}
		yTicksDict = {yLable: yi for (yi, yLable) in enumerate(yTicksList)}
		iMax = len(xTicksList)
		jMax = len(yTicksList)
		grid = [[0 for j in range(jMax)] for i in range(iMax)]
		ans = 0
		for (x1, y1, x2, y2) in rectangles:
			for i in range(xTicksDict[x1], xTicksDict[x2]):
				xSide = xTicksList[i + 1] - xTicksList[i]
				for j in range(yTicksDict[y1], yTicksDict[y2]):
					if grid[i][j] == 0:
						ans += xSide * (yTicksList[j + 1] - yTicksList[j])
						grid[i][j] = 1
		return ans % (10 ** 9 + 7)


class Solution:

	def rectangleArea(self, rectangles: List[List[int]]) -> int:
		N = len(rectangles)
		(Xvals, Yvals) = (set(), set())
		for (x1, y1, x2, y2) in rectangles:
			Xvals.add(x1)
			Xvals.add(x2)
			Yvals.add(y1)
			Yvals.add(y2)
		imapx = sorted(Xvals)
		imapy = sorted(Yvals)
		mapx = {x: i for (i, x) in enumerate(imapx)}
		mapy = {y: i for (i, y) in enumerate(imapy)}
		grid = [[0] * len(imapy) for _ in imapx]
		for (x1, y1, x2, y2) in rectangles:
			for x in range(mapx[x1], mapx[x2]):
				for y in range(mapy[y1], mapy[y2]):
					grid[x][y] = 1
		ans = 0
		for (x, row) in enumerate(grid):
			for (y, val) in enumerate(row):
				if val:
					ans += (imapx[x + 1] - imapx[x]) * (imapy[y + 1] - imapy[y])
		return ans % (10 ** 9 + 7)


from collections import defaultdict

class Solution:

	def rectangleArea(self, rectangles: List[List[int]]) -> int:

		def merge_intervals(intervals):
			if not intervals:
				return 0
			intervals.sort()
			end = intervals[0][1]
			width = end - intervals[0][0]
			for (left, right) in intervals:
				if left < end < right:
					width += right - end
					end = right
				elif left >= end:
					width += right - left
					end = right
			return width
		events = defaultdict(list)
		for (x1, y1, x2, y2) in rectangles:
			events[y1].append((1, x1, x2))
			events[y2].append((0, x1, x2))
		events = sorted(events.items(), key=lambda x: x[0])
		intervals = []
		area = width = 0
		MOD = 10 ** 9 + 7
		last_y = events[0][0]
		for (y, event) in events:
			area += (y - last_y) * width
			area %= MOD
			for (flag, x1, x2) in event:
				if flag:
					intervals.append((x1, x2))
				else:
					intervals.remove((x1, x2))
			width = merge_intervals(intervals)
			last_y = y
		return area


from functools import reduce

class Solution:

	def rectangleArea(self, rectangles: List[List[int]]) -> int:

		def intersection(a, b):
			return [max(a[0], b[0]), max(a[1], b[1]), min(a[2], b[2]), min(a[3], b[3])]

		def area(rec):
			dx = max(0, rec[2] - rec[0])
			dy = max(0, rec[3] - rec[1])
			return dx * dy
		import itertools
		a = 0
		for i in range(1, len(rectangles) + 1):
			sign = (-1) ** (i + 1)
			for k in itertools.combinations(rectangles, i):
				a += sign * area(reduce(intersection, k))
		return a % (10 ** 9 + 7)

	def rectangleArea(self, rectangles: List[List[int]]) -> int:
		xmap = [{}, {}]
		xs = [[], []]
		for i in rectangles:
			xs[0].append(i[0])
			xs[0].append(i[2])
			xs[1].append(i[1])
			xs[1].append(i[3])
		xs[0].sort()
		xs[1].sort()
		rmap = [[], []]
		for k in range(2):
			cnt = 0
			for i in xs[k]:
				if i not in xmap[k]:
					xmap[k][i] = cnt
					rmap[k].append(i)
					cnt += 1
		grid = [[0] * len(rmap[0]) for _ in range(len(rmap[1]))]
		for r in rectangles:
			for i in range(xmap[0][r[0]], xmap[0][r[2]]):
				for j in range(xmap[1][r[1]], xmap[1][r[3]]):
					grid[j][i] = 1
		area = 0
		for i in range(len(rmap[0]) - 1):
			width = rmap[0][i + 1] - rmap[0][i]
			for j in range(len(rmap[1]) - 1):
				if grid[j][i]:
					area += width * (rmap[1][j + 1] - rmap[1][j])
		return area % (10 ** 9 + 7)


import numpy as np

class Solution:

	def rectangleArea(self, A: List[List[int]]) -> int:
		sa = sorted(set((a for (x1, y1, x2, y2) in A for a in [x1, x2])))
		xs = sorted(sa)
		dic = {v: i for (i, v) in enumerate(xs)}
		B = []
		for (x1, y1, x2, y2) in A:
			B.append([y1, x1, x2, 1])
			B.append([y2, x1, x2, -1])
		B.sort()
		sum_x = ret = cur_y = 0
		ct = np.zeros(len(xs))
		for (y, x1, x2, flag) in B:
			ret += sum_x * (y - cur_y)
			cur_y = y
			ct[dic[x1]:dic[x2]] += flag
			sum_x = sum([x2 - x1 for (x1, x2, f) in zip(xs, xs[1:], ct) if f])
		return ret % (10 ** 9 + 7)


class Solution:

	def rectangleArea(self, rectangles: List[List[int]]) -> int:
		(all_x, all_y) = (set(), set())
		for (x1, y1, x2, y2) in rectangles:
			all_x.add(x1)
			all_x.add(x2)
			all_y.add(y1)
			all_y.add(y2)
		all_x = list(all_x)
		all_x.sort()
		all_y = list(all_y)
		all_y.sort()
		x_map = {val: i for (i, val) in enumerate(all_x)}
		y_map = {val: i for (i, val) in enumerate(all_y)}
		area = [[0 for _ in range(len(y_map))] for _ in range(len(x_map))]
		for (x1, y1, x2, y2) in rectangles:
			for x in range(x_map[x1], x_map[x2]):
				for y in range(y_map[y1], y_map[y2]):
					area[x][y] = 1
		ans = 0
		for x in range(len(x_map)):
			for y in range(len(y_map)):
				if area[x][y]:
					ans += (all_x[x + 1] - all_x[x]) * (all_y[y + 1] - all_y[y])
					if ans > 1000000007:
						ans %= 1000000007
		return ans


class Solution(object):

	def rectangleArea(self, rectangles):
		(OPEN, CLOSE) = (0, 1)
		events = []
		for (x1, y1, x2, y2) in rectangles:
			events.append((y1, OPEN, x1, x2))
			events.append((y2, CLOSE, x1, x2))
		events.sort()

		def query():
			ans = 0
			cur = -1
			for (x1, x2) in active:
				cur = max(cur, x1)
				ans += max(0, x2 - cur)
				cur = max(cur, x2)
			return ans
		active = []
		cur_y = events[0][0]
		ans = 0
		for (y, typ, x1, x2) in events:
			ans += query() * (y - cur_y)
			if typ is OPEN:
				active.append((x1, x2))
				active.sort()
			else:
				active.remove((x1, x2))
			cur_y = y
		return ans % (10 ** 9 + 7)


from typing import List

class Solution:

	def rectangleArea(self, rectangles: List[List[int]]) -> int:
		xs = sorted(set([x for (x1, y1, x2, y2) in rectangles for x in [x1, x2]]))
		xi = {v: i for (i, v) in enumerate(xs)}
		co = [0] * len(xs)
		ar = []
		for (x1, y1, x2, y2) in rectangles:
			ar.append([y1, x1, x2, 1])
			ar.append([y2, x1, x2, -1])
		ar.sort()
		ly = lx = res = 0
		for (y, x1, x2, sig) in ar:
			res += (y - ly) * lx
			ly = y
			for i in range(xi[x1], xi[x2]):
				co[i] += sig
			lx = sum((xs[i + 1] - xs[i] if co[i] else 0 for i in range(len(xs) - 1)))
		return res % (10 ** 9 + 7)


class Solution:

	def rectangleArea(self, rectangles: List[List[int]]) -> int:
		xs = sorted({x for (x1, _, x2, _) in rectangles for x in [x1, x2]})
		index = {v: i for (i, v) in enumerate(xs)}
		cnt = [0] * len(index)
		events = []
		for (x1, y1, x2, y2) in rectangles:
			events.append([y1, x1, x2, 1])
			events.append([y2, x1, x2, -1])
		events.sort()
		curr_y = curr_x_sum = area = 0
		for (y, x1, x2, sign) in events:
			area += (y - curr_y) * curr_x_sum
			curr_y = y
			for i in range(index[x1], index[x2]):
				cnt[i] += sign
			curr_x_sum = sum((x2 - x1 if c else 0 for (x1, x2, c) in zip(xs, xs[1:], cnt)))
		return area % (10 ** 9 + 7)


class Solution:

	def rectangleArea(self, rectangles: List[List[int]]) -> int:
		xs = sorted(set([x for (x1, y1, x2, y2) in rectangles for x in [x1, x2]]))
		x_i = {v: i for (i, v) in enumerate(xs)}
		count = [0] * len(x_i)
		L = []
		for (x1, y1, x2, y2) in rectangles:
			L.append([y1, x1, x2, 1])
			L.append([y2, x1, x2, -1])
		L.sort()
		cur_y = cur_x_sum = area = 0
		for (y, x1, x2, sig) in L:
			area += (y - cur_y) * cur_x_sum
			cur_y = y
			for i in range(x_i[x1], x_i[x2]):
				count[i] += sig
			cur_x_sum = sum((x2 - x1 if c else 0 for (x1, x2, c) in zip(xs, xs[1:], count)))
		return area % (10 ** 9 + 7)


class Solution:

	def rectangleArea(self, rectangles: List[List[int]]) -> int:
		xs = sorted(set((x for (x1, _, x2, _) in rectangles for x in [x1, x2])))
		xi = {v: i for (i, v) in enumerate(xs)}
		count = [0] * len(xs)
		lines = []
		for (x1, y1, x2, y2) in rectangles:
			lines.append((y1, x1, x2, 1))
			lines.append((y2, x1, x2, -1))
		lines.sort()
		(curr_y, x_sum, res) = (0, 0, 0)
		for (y, x1, x2, sign) in lines:
			res += x_sum * (y - curr_y)
			curr_y = y
			for i in range(xi[x1], xi[x2]):
				count[i] += sign
			x_sum = 0
			for i in range(len(xs) - 1):
				if count[i] > 0:
					x_sum += xs[i + 1] - xs[i]
		return res % (10 ** 9 + 7)


class Solution:

	def rectangleArea(self, rectangles: List[List[int]]) -> int:
		x_set = set()
		points = []
		for (x1, y1, x2, y2) in rectangles:
			x_set.add(x1)
			x_set.add(x2)
			heapq.heappush(points, (y1, x1, x2, 1))
			heapq.heappush(points, (y2, x1, x2, -1))
		x_list = sorted(list(x_set))
		mapping = {x: i for (i, x) in enumerate(x_list)}
		count = [0] * len(x_list)
		res = 0
		pre_y = points[0][0]
		while points:
			cur_y = points[0][0]
			h = cur_y - pre_y
			for i in range(len(x_list) - 1):
				if count[i] > 0:
					res += (x_list[i + 1] - x_list[i]) * h
			res %= 10 ** 9 + 7
			while points and points[0][0] == cur_y:
				(cur_y, x1, x2, cnt) = heapq.heappop(points)
				for i in range(mapping[x1], mapping[x2]):
					count[i] += cnt
			pre_y = cur_y
		return res