Fast algorithm for selecting two intervals from this set

Question

Suppose we are given a set of closed intervals where each interval is in the form of [l,r]. If we want to select two intervals from this set such that the size of their intersection times the size of their union is the maximum. Can we provide a nontrivial algorithm to solve this problem?

For example, if we have four intervals, [1,6], [4,8], [2,7], [3,5]. The optimum solution is to select [1,6] and [2,7]. The answer is (7-1) * (6-2) = 24.

Actually the original problem requires us to select (N>=2) number of intervals but I think we can prove that the optimal solution only consists of two intervals:

If the optimum solution has three or more intervals:

[                     ]
            [               ]
                   [                          ]

We can see that the weight won't decrease if we delete the middle interval.

Answer 1

Given a set of N > 2 overlapping intervals which supposedly maximises union times intersection, set aside an interval containing the leftmost point in the union and an interval containing the rightmost point in the union. Since N > 2 you have at least one other interval left. If you remove this interval from the set, you do not decrease the size of the union of intervals, because you set aside intervals to cover the leftmost and rightmost points. You can only increase the size of the intersection by removing an interval. So by removing this interval you can only increase the product you are trying to maximise, so the best solution can indeed be found at N = 2.

Sort the set of endpoints of intervals and go through it in increasing order. In case of ties, consider leftmost points before rightmost points. Keep track of a set of intervals, adding an interval to the set when you see its leftmost point, and removing an interval from the set when you see its rightmost point.

For any two overlapping intervals, there will be a point when one of them is already present and you are just about to add the other one. So if, just before you add an interval to the set, you compare it with all other intervals already in the set, you can compare all pairs of overlapping intervals. You can therefore compute the product of union and intersection between the interval about to be added and all other intervals in the set and keep track of the largest one seen.