Fast algorithm for selecting two intervals from this set

Question

Suppose we are given a set of closed intervals, where each interval has the form [l, r]. If we want to select two intervals from this set, so that the size of their intersections, the size of their union is maximum . Can we provide a non-trivial algorithm to solve this problem?

For example, if we have four intervals, [1,6], [4,8], [2,7], [3,5]. The optimal solution is the choice of [1.6] and [2.7]. Answer: (7-1) * (6-2) = 24.

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

If the optimal solution has three or more intervals:

[ ] [ ] [ ] 

We can see that the weight will not decrease if we remove the average interval.

Answer 1

Given the many N> 2 overlapping intervals that supposedly maximize the intersection of the join times, defer the interval containing the left-most join point and the interval containing the right-most point in the join. Since N> 2, you have at least one remaining interval. If you remove this interval from the set, you do not reduce the size of the union of the intervals, because you defer the intervals to cover the leftmost and rightmost points. You can increase the size of the intersection by deleting the interval. Thus, by removing this interval, you can only increase the product that you are trying to maximize, so the best solution can really be found in N = 2.

Sort the set of endpoints of the intervals and go through it in ascending order. For links, look at the leftmost points in front of the rightmost points. Keep track of the set of intervals by adding an interval to the set when you see its leftmost point, and remove the 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 going to add the other. Therefore, if before adding an interval to a set, you compare it with all other intervals already set in the set, you can compare all pairs of overlapping intervals. Therefore, you can calculate the product of the union and intersection between the interval to be added and all the other intervals in the set and track the largest of them.

Answer 2

Proof that two intervals are enough: it makes no sense to choose an interval that is correctly contained in another interval. Without loss of generality, let the intervals be [a1, b1], ..., [an, bn] such that a1 <... <ap. If no interval properly contains another interval, then b1 <... <billion. For i <j <k, he believes that ([ai, bi] intersect [aj, bj] intersect [ak, bk]) = ([ai, bi] intersect [ak, bk]) and are the same for the union, so there is no reason to choose more than two intervals.

O (n log n) -time algorithm:, the problem is to find the intervals [a, b] and [c, d] of maximization (d - a) * (b - c), since this product is negative if intervals do not intersect. Our algorithm is to pre-process O (n log n), which allows us to find the best helper for each interval in O (log n) time.

Let the job of finding the best helper for [a, b]. Take some algebra: (d - a) * (b - c) = d * b - d * c - a * b + a * c. Since a, b are fixed, we can drop the term -a * b and maximize the scalar product <(a, b, 1), (d, c, -d * c)> over all intervals [c, d], since the set of vectors (d, c, -d * c) is fixed, this essentially simulates the collision of a stationary polyhedron and a moving plane perpendicular to (a, b, 1). Thanks to Edelsbrunner and Maurer ( Finding Extreme Points in Three Dimensions and Solving the Mail Branch Problem in the Plane , 1984), there is an algorithm that preprocesses in time O (n log n) and solves queries of this type for different a and b in O (log n ) time.

One of the sour details is that we must choose at least two intervals, but the best “solution” may be the longest interval with ourselves. I'm sure this is messy, but it's possible to expand Edelsbrunner - Maurer to find the second most extreme point in the same run time.