LeetCode850.RectangleAreaII

class Solution {
public:
    struct interval {
        int start, end;
        bool operator<(const interval &i) const {
            if (start == i.start)
                return end < i.end;
            return start < i.start;
        }
    };
    
    struct edge {
        int x;
        interval i;
        int type; // left <- 1, right <- -1
        int id;
    };
    
    int rectangleArea(vectorint>>& rectangles) {
        vector vec;
        for (int i=0;ii){
            auto rect=rectangles[i];
            vec.push_back({rect[0],{rect[1],rect[3]},1,i});
            vec.push_back({rect[2],{rect[1],rect[3]},-1,i});
        }
        sort(vec.begin(),vec.end(),[](edge e1, edge e2){
            return e1.x < e2.x;
        });
        
        setint>> active_set; // 
        active_set.insert({vec[0].i,vec[0].id});
        int prev_x=vec[0].x;
        
        int res=0;
        for (int i=1;ii){
            int delta_x=vec[i].x-prev_x;
            
            // merge interval
            int s=-1,e=-1;
            int total_y=0;
            for (auto m:active_set){
                interval i=m.first;
                int id=m.second;
                if (s==-1 || i.start>e){
                    total_y += e-s;
                    s = i.start; e = i.end;
                }else{
                    e = max(e,i.end);
                }
            }
            total_y += e-s;
            
            res = (res + long(delta_x)*total_y) % 1000000007;
            
            if (vec[i].type==1) active_set.insert({vec[i].i,vec[i].id});
            else active_set.erase({vec[i].i,vec[i].id});
            
            prev_x = vec[i].x;
        }
        return res;
    }
};