Daily LeetCode – day0049 0850. Rectangle Area II

import java.util.ArrayList;
import java.util.List;
import java.util.TreeMap;

// 0850. Rectangle Area II
class Solution {
    public int rectangleArea(int[][] rectangles) {
        int ans = 0;
        int L = 1;
        int R = -1;
        int px = 0;
        int M = 1000000007;
        TreeMap<Integer, List<int[]>> map = new TreeMap<>();
        TreeMap<Integer, Integer> ymap = new TreeMap<>();
        for (int i = 0; i < rectangles.length; i++) {
            map.computeIfAbsent(rectangles[i][0], o -> new ArrayList<>()).add(new int[]{i, L});
            map.computeIfAbsent(rectangles[i][2], o -> new ArrayList<>()).add(new int[]{i, R});
        }
        for (int x : map.keySet()) {
            int py = 0, cnt = 0, sum = 0;
            for (int y : ymap.keySet()) {
                if (cnt > 0) {
                    sum += y - py;
                }
                py = y;
                cnt += ymap.get(y);
            }
            ans += (long) (x - px) * sum % M;
            ans %= M;
            px = x;
            for (int[] m : map.get(x)) {
                ymap.merge(rectangles[m[0]][1], m[1], Integer::sum);
                ymap.merge(rectangles[m[0]][3], m[1] * -1, Integer::sum);
            }
        }
        return ans;
    }
}

学习笔记：
这是一道超级困难题，就需要横向和纵向都使用线性扫描。
光横向x轴线性扫描就够烦的了，要考虑很多东西，怎么排序的细节。