Best algorithm to find "deepest" interval

Question

Let's say I have a list of intervals on a number line. The "depth" of a point on this number line corresponds to the number of intervals in the list that contain it [the point].

So for instance if I have the intervals [(1, 8), (3, 12), (4,6)], the deepest points comprise the interval (4, 6).

What is the fastest algorithm to find a point of max depth (just one is fine)?

Answer 1

Here's an n log n algorithm:

1. Convert the intervals into a sorted collection of start and end events. O(n log n)

2. Initialize a depth value and deepest value to zero, and iterate the collection in sorted order. O(n)

3. When you encounter a start event, increment your depth value.

   • If it's greater than the deepest you've seen, update your deepest and save the current value along the number line as your candidate point (or the start of a candidate interval)

   When you encounter an end event, decrement your depth value.

   • If you were tracking a candidate interval, and the current depth is less than the deepest depth when you're done processing all intervals that start/end here, then this is the end of your candidate interval.

Return the last (deepest) candidate point or interval you found.

(I've elided a little complexity for handling open versus closed intervals, but both can be accommodated with an appropriate tie-breaker rule for coincident start/end events.)

(You can improve the constants by having two collections, a collection of starts and a collection of ends, walking through them together. But that doesn't change the asymptotic analysis.)

---

I looked at a divide and conquer algorithm too, but it had the same O(n log n) and fussier case handling for merging the results for each half, so ordered traversal might be the neatest way if it's feasible for your data set.