1
struct Point {
2
  int X;
3
  int delta;
4
};
5

6
class Solution {
7
 public:
8
  int rectangleArea(vector<vector<int>> &rectangles) {
9
    map<int, vector<Point>> lines; // y -> array of Points
10
    for (auto &r : rectangles) {
11
      auto x1 = r[0];
12
      auto y1 = r[1];
13
      auto x2 = r[2];
14
      auto y2 = r[3];
15

16
      lines[y1].push_back(Point{x1, +1});
17
      lines[y1].push_back(Point{x2, -1});
18
      lines[y2].push_back(Point{x1, -1});
19
      lines[y2].push_back(Point{x2, +1});
20
    }
21

22
    long area = 0;
23
    int prevy = 0;
24
    int length = 0;
25

26
    map<int, int> scanline; // x -> delta
27
    for (const auto &[y, points] : lines) {
28
      area += (y - prevy) * (long)length;
29

30
      // Update scanline for new y: add new rectanhgles,
31
      // remove old
32
      for (auto point : points) {
33
        auto xdelta = scanline.find(point.X);
34
        if (xdelta != end(scanline)) {
35
          xdelta->second += point.delta;
36
          if (xdelta->second == 0) scanline.erase(xdelta);
37
        } else
38
          scanline[point.X] = point.delta;
39
      }
40

41
      // For current y-line calc the length of
42
      // intersection with rectangles
43
      int startX = -1;
44
      int rectCount = 0;
45
      length = 0;
46
      for (const auto &[x, delta] : scanline) {
47
        int oldcount = rectCount;
48
        rectCount += delta;
49
        if (oldcount == 0)
50
          startX = x;
51
        else if (rectCount == 0)
52
          length += x - startX;
53
      }
54

55
      if (rectCount > 0) length += scanline.rbegin()->first - startX;
56

57
      prevy = y;
58
    }
59

60
    return area % (1000000007);
61
  }
62
};