Union of closed intervals on $\mathbb{R}$

Question

Suppose there are multiple intervals on $\mathbb{R}$, e.g., $[0,0.5]$, $[0.4,1]$, $[1.5,2]$, the union of them should be $[0,1]$ and $[1.5,2]$. Is there a specific datastructure (or algorithm) for computing such union?

A variation of this problem is to union intervals on cyclic domain, for example, angles from $-\pi$ to $\pi$. Now, $[-\pi/2, \pi/2]$ and $[\pi/2, -\pi/2]$ present different intervals of angles.

I have coded a brute force algorithm, however, I am wondering there already exist studies on this.

Answer 1

If you order the intervals by their starting point (possible with complexity ${\cal O}(N \log N)$), then you can test whether adjacent intervals overlap and merge them as necessary in ${\cal O}(N)$ operations. What you end up with is list of disjoint intervals.

To do this in a periodic domain is only marginally more difficult -- do the same as above, and at the end of the operations see if you can merge the first and the last of the merged intervals.