Today I was solving a problem which reminded me that I still don't know an efficient algorithm for finding the area of the union of large number of rectangles (all rectangles are with sides parallel to the axes). I was looking for a tutorial and the best I found was an article from topcoder which only mentions the existence of such algorithm and presents an O(N^2logN) sweep line + BST algorithm. Can someone please tell me how to solve this faster — O(NlogN) or something like that. I thought about sweep line with segment tree in which I need to update an interval with 1 or -1 and get the number of zeroes over the whole interval but I couldn't come up with a way to do it.
Thanks in advance! :)