Approach
Sorting and greedy selection
For Rectangle Area II, the implementation first exposes a useful order, then scans that order while making locally justified choices.
- Choose the key that reveals the greedy or grouping structure.
- Sort the relevant records by that key.
- Scan in order, maintaining the invariant that makes each local choice safe.
Code notes
- 39 lines of Python from the credited upstream file 850.py.
- The implementation visibly relies on sequence storage.
- No explicit loop blocks detected.
Complexity
Sorting is typically the dominant term unless the subsequent scan uses a more expensive nested operation.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1class Solution:2 def rectangleArea(self, rectangles: list[list[int]]) -> int:3 events = []4 5 for x1, y1, x2, y2 in rectangles:6 events.append((x1, y1, y2, 's'))7 events.append((x2, y1, y2, 'e'))8 9 events.sort(key=lambda x: x[0])10 11 ans = 012 prevX = 013 yPairs = []14 15 def getHeight(yPairs: list[tuple[int, int]]) -> int:16 height = 017 prevY = 018 19 for y1, y2 in yPairs:20 prevY = max(prevY, y1)21 if y2 > prevY:22 height += y2 - prevY23 prevY = y224 25 return height26 27 for currX, y1, y2, type in events:28 if currX > prevX:29 width = currX - prevX30 ans += width * getHeight(yPairs)31 prevX = currX32 if type == 's':33 yPairs.append((y1, y2))34 yPairs.sort()35 else: 36 yPairs.remove((y1, y2))37 38 return ans % (10**9 + 7)39