Leetcode 850: Rectangle Area II

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

Notes:

One way to solve this problem is Line Sweep method. The basic idea to the scan X axis or the Y axis "line by line". Let choose Y axis. So we need to sort them by Y value, and then start with the smallest one. So the sweeping is from the bottom,

1): For each Y value, we need to determine what is the "effective intervals" in X. Now the question is lowered into 1 D problem, and it can be solved as Merge Interval;

2): After obtain the effective X, we need to calculate the Y interval. We just need to go to the next Y value. The difference is the delta_Y for this specific interval;

3): This part of area can be calculated as effective X * delta_Y;

3): For rectangle, we need to know when it starts and when it stops in the process of sweeping. It seems not easy, but actually it is. We just need to label them as "active" when the lower Y edge is swept, and then label them as "inactive" when the upper Y edge is swept.

See the code below,

class Solution {
public:
    int rectangleArea(vector<vector<int>>& rectangles) {
        long res = 0;
        vector<vector<int>> cts;
        for(auto &a : rectangles) {
            cts.push_back({a[1], a[0], a[2], 1});//1 represents in
            cts.push_back({a[3], a[0], a[2], -1});//-1 represents out
        }
        sort(cts.begin(), cts.end());
        int pre_y = cts[0][0];
        vector<vector<int>> ats;//active {x1, x2}; set may be a better choice.
        for(auto &a : cts) {
            int cur_y = a[0], x1 = a[1], x2 = a[2], in = a[3], cur_x = -1;
            long sum_x = 0;
            for(auto &xs : ats) {//calculate the active length in x;
                cur_x = max(cur_x, xs[0]);
                sum_x += max(xs[1] - cur_x, 0);
                cur_x = max(cur_x, xs[1]);
             }
            res += (cur_y - pre_y)*sum_x;
            if(in == 1) {
                ats.push_back({x1, x2});
                sort(ats.begin(), ats.end());
            }
            else {
                for(int i=0; i<ats.size(); ++i) {
                    if(ats[i][0] == x1 && ats[i][1] == x2) ats.erase(ats.begin()+i);
                  //  break;//there could be more than one...
                }
            }
            pre_y = cur_y;
        }
        res %= (int)(1e9 + 7);
        return (int) res;
    }
};

This question is in someway similar to the Skyline question. Thus the follow up question, how to calculate the "skyline" of these rectangles?