850. Rectangle Area II

https://leetcode.com/problems/rectangle-area-ii/

二维坐标系里有一些可能重叠的长方形，问它们形成的总面积。题目看着和skyline很像，重叠问题可以用排序+扫描线解。对每个x，求是第一条边的y去重后有效的长度。维持一个对所有x global的treemap让遍历到的所有y在里头排好序，长方形第一条竖边的入+1出-1; 第二条边反过来，入-1出+1，用于去除第一条边的记录, 遍历到sum > 0时记录下y和上个遍历的y差作为有效长度。比如两个有重叠的第一条边会成为[1 1 -1 -1], 那么[1 1], [1-1]和[-1-1]之间长度都会成功算入。如果当前x没有新长方形，那遍历求和会不断把所有可能的y置为0，比如例子中两个第二条边并入 [1(-1) 1(-1) -1(1) -1(1)]。

参考自这。

/*
 * @lc app=leetcode id=850 lang=cpp
 *
 * [850] Rectangle Area II
 *
 * https://leetcode.com/problems/rectangle-area-ii/description/
 *
 * algorithms
 * Hard (45.33%)
 * Likes:    213
 * Dislikes: 23
 * Total Accepted:    8K
 * Total Submissions: 17.5K
 * Testcase Example:  '[[0,0,2,2],[1,0,2,3],[1,0,3,1]]'
 *
 * 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 Solution {
public:
    class Point {
    public:
        int x, y, val;
        Point(int x, int y, int val): x(x), y(y), val(val) {}
    };
    int rectangleArea(vector<vector<int>>& rectangles) {
        const int M = 1000000007;
        vector<Point> points;
        for (const auto &r : rectangles) {
            points.push_back(Point(r[0], r[1], 1));
            points.push_back(Point(r[0], r[3], -1));
            points.push_back(Point(r[2], r[1], -1));
            points.push_back(Point(r[2], r[3], 1));
        }
        sort(points.begin(), points.end(), [](Point &a, Point &b) {
            return a.x < b.x;
        });
        const auto cal_y = [](map<int, int> &m) {
            int res = 0, pre = -1, sum = 0;
            for (const auto &p : m) {
                if (sum > 0) res += p.first - pre;
                sum += p.second;
                pre = p.first;
            }
            return res;
        };
        map<int, int> m;
        const int N = points.size();
        int pre_x = -1, pre_y = -1, res = 0;
        for (int i = 0; i < N; ++i) {
            Point &p = points[i];
            if (!m.count(p.y)) m[p.y] = 0;
            m[p.y] += p.val;
            if (i == N - 1 || points[i + 1].x > p.x) {
                if (pre_x > -1) {
                    res += ((long)pre_y * (p.x - pre_x)) % M;
                    res %= M;
                }
                pre_y = cal_y(m);
                pre_x = p.x;
            }

        }
        return res;
    }
};