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

https://leetcode.com/problems/rectangle-area-ii/discuss/137941/Java-TreeMap-solution-inspired-by-Skyline-and-Meeting-Room

class Solution {
    class Point {
        int x, y, s;
        Point(int x, int y, int s) {
            this.x = x;
            this.y = y;
            this.s = s;
        }
    }
    public int rectangleArea(int[][] rectangles) {
        Map<Integer, Integer> map = new TreeMap<>((a,b) -> a - b); //sort key increasingly
        List<Point> points = new ArrayList<>();
        for (int[] rec: rectangles) {
            Point p1 = new Point(rec[0],rec[1],1);
            Point p2 = new Point(rec[2],rec[1],-1);
            Point p3 = new Point(rec[0],rec[3],-1);
            Point p4 = new Point(rec[2],rec[3],1);
            points.add(p1);
            points.add(p2);
            points.add(p3);
            points.add(p4);
        }
        Collections.sort(points,(a,b) -> a.y - b.y);//sort by y increasingly
        int preY = points.get(0).y;
        long ans = 0;
        for (int i = 0; i < points.size(); i++) {
            Point p = points.get(i);
            if (p.y == preY) {// for each y, create a map for xs recording x's status
                map.put(p.x, map.getOrDefault(p.x,0) + p.s);  //<x,x's current status -+1>
            } else {
                long interval = calX(map);// calculate x effective length
                ans += interval * (p.y - preY); // add area;
                preY = p.y; 
                i--; // keep in current point if in new layer, p.y != preY then start from it in next iteration
            }
        }
        ans = ans % (1000000000+7);
        return (int)ans;
    }

    public long calX(Map<Integer,Integer> map) {
        int count = 0; //count = 0 means no effective interval 
        int prex = -1; 
        long ans = 0;
        for (Map.Entry<Integer,Integer> e : map.entrySet()) {
            if (count > 0) {
                ans += e.getKey() - prex; //add interval
            } 
            count += e.getValue(); // move forward
            prex = e.getKey();
        }
        return ans;
    }
}