<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>

#define MOD 1000000007

class Solution {
public:
    int rectangleArea(vector<vector<int>>& rectangles) {
        vector<tuple<int64_t, int64_t, int64_t, int>> events;
        for (auto& rect : rectangles) {
            events.push_back(make_tuple(rect[1], rect[0], rect[2], 0));
            events.push_back(make_tuple(rect[3], rect[0], rect[2], 1));
        }

        sort(events.begin(), events.end());
        multiset<pair<int64_t, int64_t>> intervals;
        int idx = 0;
        int64_t y = 0;
        int64_t width = 0;
        int64_t area = 0;

        while (idx < events.size()) {
            int64_t new_y = get<0>(events[idx]);
            area = (area + ((new_y - y) * width) % MOD) % MOD;
            while (idx < events.size() && get<0>(events[idx]) == new_y) {
                auto interval = make_pair(get<1>(events[idx]), get<2>(events[idx]));
                if (get<3>(events[idx]))
                    intervals.erase(intervals.lower_bound(interval));
                else
                    intervals.insert(interval);
                idx++;
            }

            vector<pair<int64_t, int64_t>> intervals_s(intervals.begin(), intervals.end());
            sort(intervals_s.begin(), intervals_s.end());

            int64_t new_width = 0;
            int64_t int_l = 0;
            int64_t int_r = 0;
            for (auto interval : intervals_s) {
                if (interval.first <= int_r) {
                    int_r = max(int_r, interval.second);
                } else {
                    new_width += int_r - int_l;
                    int_l = interval.first;
                    int_r = interval.second;
                }
            }
            width = new_width + (int_r - int_l);
            y = new_y;
        }

        return area;
    }
};
12700