<p>You are given a 2D array of axis-aligned <code>rectangles</code>. Each <code>rectangle[i] = [x<sub>i1</sub>, y<sub>i1</sub>, x<sub>i2</sub>, y<sub>i2</sub>]</code> denotes the <code>i<sup>th</sup></code> rectangle where <code>(x<sub>i1</sub>, y<sub>i1</sub>)</code> are the coordinates of the <strong>bottom-left corner</strong>, and <code>(x<sub>i2</sub>, y<sub>i2</sub>)</code> are the coordinates of the <strong>top-right corner</strong>.</p>

<p>Calculate the <strong>total area</strong> covered by all <code>rectangles</code> in the plane. Any area covered by two or more rectangles should only be counted <strong>once</strong>.</p>

<p>Return <em>the <strong>total area</strong></em>. Since the answer may be too large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://s3-lc-upload.s3.amazonaws.com/uploads/2018/06/06/rectangle_area_ii_pic.png" style="width: 600px; height: 450px;" />
<pre>
<strong>Input:</strong> rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
<strong>Output:</strong> 6
<strong>Explanation:</strong> A total area of 6 is covered by all three rectangles, as illustrated in the picture.
From (1,1) to (2,2), the green and red rectangles overlap.
From (1,0) to (2,3), all three rectangles overlap.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> rectangles = [[0,0,1000000000,1000000000]]
<strong>Output:</strong> 49
<strong>Explanation:</strong> The answer is 10<sup>18</sup> modulo (10<sup>9</sup> + 7), which is 49.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= rectangles.length &lt;= 200</code></li>
	<li><code>rectanges[i].length == 4</code></li>
	<li><code>0 &lt;= x<sub>i1</sub>, y<sub>i1</sub>, x<sub>i2</sub>, y<sub>i2</sub> &lt;= 10<sup>9</sup></code></li>
	<li><code>x<sub>i1 &lt;= </sub>x<sub>i2</sub></code></li>
	<li><code>y<sub>i1 &lt;=</sub> y<sub>i2</sub></code></li>
</ul>

struct Event {
  int x;
  int y1;
  int y2;
  char type;
};

class Solution {
 public:
  int rectangleArea(vector<vector<int>>& rectangles) {
    constexpr int kMod = 1'000'000'007;

    vector<Event> events;

    for (const vector<int>& r : rectangles) {
      events.emplace_back(r[0], r[1], r[3], 's');
      events.emplace_back(r[2], r[1], r[3], 'e');
    }

    ranges::sort(events, ranges::less{},
                 [](const Event& event) { return event.x; });

    long ans = 0;
    int prevX = 0;
    vector<pair<int, int>> yPairs;

    for (const auto& [currX, y1, y2, type] : events) {
      if (currX > prevX) {
        const int width = currX - prevX;
        ans = (ans + width * getHeight(yPairs)) % kMod;
        prevX = currX;
      }
      if (type == 's') {
        yPairs.emplace_back(y1, y2);
        ranges::sort(yPairs);
      } else {  // type == 'e'
        const auto it =
            find(yPairs.begin(), yPairs.end(), pair<int, int>(y1, y2));
        yPairs.erase(it);
      }
    }

    return ans % kMod;
  }

 private:
  long getHeight(const vector<pair<int, int>>& yPairs) {
    int height = 0;
    int prevY = 0;

    for (const auto& [y1, y2] : yPairs) {
      prevY = max(prevY, y1);
      if (y2 > prevY) {
        height += y2 - prevY;
        prevY = y2;
      }
    }

    return height;
  }
};
11700