python3 解法, 执行用时: 60 ms, 内存消耗: 16.2 MB, 提交时间: 2023-07-27 09:18:13

MOD = int(1e9 + 7)
class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        xs, ans = set(), 0
        for x0, _, x1, _ in rectangles:
            xs.add(x0)
            xs.add(x1)
        # 纵向x轴扫描线
        for a, b in pairwise(sorted(xs)):
            ys = [(y0, y1) for x0, y0, x1, y1 in rectangles if x0 <= a and b <= x1]
            s = cur = 0
            # 横向y轴扫描线
            for c, d in sorted(ys, key=lambda x: (x[0], -x[1])):
                if c > cur:
                    s += d - c
                elif d > cur:
                    s += d - cur
                cur = max(cur, d)
            ans = (ans + s * (b - a)) % MOD
        return ans

cpp 解法, 执行用时: 100 ms, 内存消耗: 17.5 MB, 提交时间: 2023-07-27 09:16:41

// 暴力切块
class Solution {
public:
    int rectangleArea(vector<vector<int>>& rectangles) {
        const int MOD = 1e9+7;
        int n = rectangles.size();
        unordered_set<int> st;
        for (int i=0;i<n;i++) {
            st.insert(rectangles[i][0]);st.insert(rectangles[i][2]);
        }    
        vector<int> sweeps(st.begin(),st.end());
        sort(sweeps.begin(),sweeps.end());
        st.clear();
        for (int i=0;i<n;i++) {st.insert(rectangles[i][1]); st.insert(rectangles[i][3]);};
        vector<int> hbounds(st.begin(),st.end());
        sort(hbounds.begin(),hbounds.end());
        int m = hbounds.size();
        long long ans = 0;
        for (int i=0;i<sweeps.size()-1;i++) {
            for (int j=0;j<m-1;j++) {
                vector<int> rect = { sweeps[i],hbounds[j], sweeps[i+1],hbounds[j+1] };
                if (check(rect,rectangles)) ans += (long long)( hbounds[j+1] - hbounds[j]) *  (sweeps[i+1] - sweeps[i] );
            }
            ans %= MOD;
        }
        return ans;
    }

    bool check(vector<int> & rect, vector<vector<int>>& rectangles) {
        int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
        for (auto &r:rectangles) {
            if ( x1>=r[0] and x1<=r[2] and x2>=r[0] and x2<=r[2] and y1>=r[1] and y1<=r[3] and y2>=r[1] and y2<=r[3] )
                return true;
        }
        return false;
    }
};

python3 解法, 执行用时: 60 ms, 内存消耗: 16.2 MB, 提交时间: 2023-07-27 09:15:16

# 线段树 + 扫描线
class Node:
    def __init__(self):
        self.l = self.r = 0
        self.cnt = self.length = 0


class SegmentTree:
    def __init__(self, nums):
        n = len(nums) - 1
        self.nums = nums
        self.tr = [Node() for _ in range(n << 2)]
        self.build(1, 0, n - 1)

    def build(self, u, l, r):
        self.tr[u].l, self.tr[u].r = l, r
        if l != r:
            mid = (l + r) >> 1
            self.build(u << 1, l, mid)
            self.build(u << 1 | 1, mid + 1, r)

    def modify(self, u, l, r, k):
        if self.tr[u].l >= l and self.tr[u].r <= r:
            self.tr[u].cnt += k
        else:
            mid = (self.tr[u].l + self.tr[u].r) >> 1
            if l <= mid:
                self.modify(u << 1, l, r, k)
            if r > mid:
                self.modify(u << 1 | 1, l, r, k)
        self.pushup(u)

    def pushup(self, u):
        if self.tr[u].cnt:
            self.tr[u].length = self.nums[self.tr[u].r + 1] - \
                self.nums[self.tr[u].l]
        elif self.tr[u].l == self.tr[u].r:
            self.tr[u].length = 0
        else:
            self.tr[u].length = self.tr[u << 1].length + \
                self.tr[u << 1 | 1].length

    @property
    def length(self):
        return self.tr[1].length


class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        segs = []
        alls = set()
        for x1, y1, x2, y2 in rectangles:
            # 矩形左侧线段
            segs.append((x1, y1, y2, 1))
            # 矩形右侧线段
            segs.append((x2, y1, y2, -1))
            # 存储所有出现过的 Y 坐标
            alls.update([y1, y2])

        segs.sort()

        # Y 坐标排序，离散化
        alls = sorted(alls)
        tree = SegmentTree(alls)
        m = {v: i for i, v in enumerate(alls)}
        ans = 0
        for i, (x, y1, y2, k) in enumerate(segs):
            if i:
                # Y 坐标被覆盖的长度 乘以 相邻横坐标之差
                ans += tree.length * (x - segs[i - 1][0])
            tree.modify(1, m[y1], m[y2] - 1, k)
        ans %= int(1e9 + 7)
        return ans