Create rectangle-area-ii.py

kamyu104 · kamyu104 · commit f15d44f1f0ca · 2018-06-10T17:36:18.000+08:00
diff --git a/Python/rectangle-area-ii.py b/Python/rectangle-area-ii.py
@@ -0,0 +1,91 @@
+# Time:  O(logn)
+# Space: O(n)
+
+# 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.
+
+
+class SegmentTreeNode(object):
+    def __init__(self, start, end):
+        self.start, self.end = start, end
+        self.total = self.count = 0
+        self._left = self._right = None
+
+    def mid(self):
+        return (self.start+self.end) // 2
+
+    def left(self):
+        self._left = self._left or SegmentTreeNode(self.start, self.mid())
+        return self._left
+
+    def right(self):
+        self._right = self._right or SegmentTreeNode(self.mid(), self.end)
+        return self._right
+
+    def update(self, X, i, j, val):
+        if i >= j:
+            return 0
+        if self.start == i and self.end == j:
+            self.count += val
+        else:
+            self.left().update(X, i, min(self.mid(), j), val)
+            self.right().update(X, 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(object):
+    def rectangleArea(self, rectangles):
+        """
+        :type rectangles: List[List[int]]
+        :rtype: int
+        """
+        OPEN, CLOSE = 1, -1
+        events = []
+        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)}
+
+        st = SegmentTreeNode(0, len(X)-1)
+        result = 0
+        cur_x_sum = 0
+        cur_y = events[0][0]
+        for y, typ, x1, x2 in events:
+            result += cur_x_sum * (y-cur_y)
+            cur_x_sum = st.update(X, Xi[x1], Xi[x2], typ)
+            cur_y = y
+        return result % (10**9+7)
