Довольно просто решить за O(N^3).
Пусть координаты k-го прямоугольника - (x1[k],x2[k],y1[k],y2[k]).
Берёте все x1,x2 (их 2*N штук), сортируете, выкидываете одинаковые. Это проекции вершин на ось X. Обозначим полученный массив A.
Аналогично с y1,y2 - получается массив B (тоже длиной не больше 2*N).
Теперь перебираем прямоугольники C=[A[p],A[p+1]]*[B[q],B[q+1]] для всех p,q. Ни один из них не пересекается сторонами исходных прямоугольников, так что если центр C лежит в одном из исходных прямоугольников, то весь прямоугольник принадлежит объединению, если нет - то не имеет с ним общих внутренних точек. Суммируем площади всех прямоугольников, принадлежащих объединению, и пишем ответ.
Можно соптимизировать до O(N^2). Насчёт O(N*log(N)) не знаю.
