Compute lebesgue measure of set of intervals

Question

Let $S = \{ [x_1, y_1], [x_2, y_2], \dots, [x_n, y_n] \}$ be a set of not necessarily disjoint intervals on $\mathbb{R}$. Is there an efficient way to compute the lebesgue measure of the union $\displaystyle \bigcup_{i = 1}^n [x_i, y_i]$ ?

I present my ideas and approaches as following.

If all intervals of $S$ are disjoint (special case), the problem is trivial and may be solved in time $\mathcal{O}(n)$. The solution is obviously $\sum_{i = 1}^n y_i - x_i$ .

In the general case, we can remove intersections as long as possible. After this procedure, we apply the special case described above. There raise up two questions:

• How to find and remove intersections?
• How efficient is this solution in terms of runtime complexity?

Another approach is to sort the intervals of $S$ by $x_i$ or $y_i$. It seems to be a good way to simplify the problem, but does it really help and how? There are several cases we must consider: disjoint intervals, overlappings, intervals completely contained in another, ...

It should be noticed that I am interested in an efficient solution. Can we do in time $\mathcal{O}(n)$ and why or why not?

I appreciate hints and references for further reading as well as solutions.