850. Rectangle Area II

• 题目链接850. Rectangle Area II
• 题目意思
  • 给出一些矩形，这些矩形可能会重叠，求矩形所围成图形的面积。
• 题目解答
  • 寒给出的一种解法
    
• 步骤
  • 延y轴扫描
    • y = 0, 底 3 = 3 - 0， 高 y = 0,
    • y = 1, 底 2 = 2 - 0， 高 y = 1, 面积 前底 3 x (当前高1 - 前高0) = 3；
    • y = 2, 底 2 = 2 - 0， 高 y = 2, 面积 前底 2 x (当前高2 - 前高1) = 2；
    • …
  • 怎么算底呢？我们可以用合并区间的方式，如合并y=0时的各个底边(0,2), (1,2), (1,3),可以按照最前的元素排序区间，在合并这些区间。

   public int rectangleArea(int[][] rectangles) {
       int OPEN = 0, CLOSE = 1;
       int[][] events = new int[rectangles.length * 2][];
       int t = 0;
       for (int[] rect : rectangles) {
           events[t++] = new int[]{rect[1], OPEN, rect[0], rect[2]};
           events[t++] = new int[]{rect[3], CLOSE, rect[0], rect[2]};
       }
       Arrays.sort(events, (a,b)->Integer.compare(a[0], b[0]));
       List<int[]> active = new ArrayList<>();
       int cur_y = events[0][0];
       long res = 0;
       for (int[] event : events) {
           int y = event[0], type = event[1], x1 = event[2], x2 = event[3];
           long query = 0;
           int cur = -1;
           // 合并区间
           for (int[] act : active) {
               cur = Math.max(cur, act[0]);
               query += Math.max(act[1] - cur, 0);
               cur = Math.max(cur, act[1]);
           }
           res += query * (y - cur_y);
           if (type == OPEN) {
               active.add(new int[]{x1, x2});
               Collections.sort(active, (a, b) -> Integer.compare(a[0], b[0]));
           } else {
               for (int i = 0; i < active.size(); i++) {
                   if (active.get(i)[0] == x1 && active.get(i)[1] == x2) {
                       active.remove(i);
                       break;
                   }
               }
           }
           cur_y = y;
       }
       res %= 1_000_000_007;
       return (int)res;
   }