Finding the total area formed by the union of the rectangles?

Question

C++ / C#

I really don't understand how to solve this problem.
Finding the total area of ​​all rectangles is an easy, obvious algorithm. But what if they intersect?
For example, I have 5 rectangles. 5 rectangle lies on 3 and 4. From which one should I calculate the total area? What if there are 100 of them? If you use conditions, you get only a sequence. The 2nd will be calculated from the 1st, the 3rd from the 2nd, the 4th from the 3rd. If you use a cycle, then the 5th can generally be calculated immediately from the 1st.

Answer 1

Clarification.
Total area (covered)?
or the total area of ​​the intersection?

Answer 2

Pretty easy to solve in O(N^3).
Let the coordinates of the kth rectangle be (x1[k],x2[k],y1[k],y2[k]).
Take all x1,x2 (there are 2*N of them), sort, throw out the same ones. These are the projections of the vertices on the X axis. Let's denote the resulting array A.
Similarly with y1,y2 - we get the array B (also no more than 2*N long).
Now iterate over the rectangles C=[A[p],A[p+1]]*[B[q],B[q+1]] for all p,q. None of them is intersected by the sides of the original rectangles, so if the center C lies in one of the original rectangles, then the entire rectangle belongs to the union, if not, then it has no common internal points with it. We sum up the areas of all the rectangles belonging to the union and write the answer.
Can be optimized to O(N^2). About O(N*log(N)) I don't know.