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.

Answer 1

You can solve this in $O(n \log n)$ time. Here is an algorithm. Sort the intervals by their left endpoint ($x$-value), in increasing value. At each stage, if the first interval is disjoint from the second interval, remove the first interval and add its width to the running total so far. If they're not disjoint, replace the first two intervals by their union.