0
$\begingroup$

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)?

$\endgroup$
2
  • 2
    $\begingroup$ You defined a depth for points. But what is a depth of an inverval? Can you please also define that? $\endgroup$
    – nir shahar
    Oct 23, 2021 at 10:28
  • $\begingroup$ Yes I see how this could be confusing... I've reworded the question to get to what I'm really interested in. $\endgroup$
    – Dincio
    Oct 23, 2021 at 11:32

1 Answer 1

8
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ can you please explain Convert the intervals into a sorted collection of start and end events. sorting? I'm confused with pair sorting $\endgroup$
    – Akash KC
    Oct 28, 2021 at 17:31
  • 1
    $\begingroup$ It's not a pair. The interval [3, 6] is two separate events: (Start Event: value = 3) and (End Event: value = 6). You can sort this collection of events by their values. Or, as I mention later, you can put all the start events into one min heap / sorted list, and all the end events into their own min heap / sorted list, and walk the two sorted collections, popping whichever is least at each step. $\endgroup$
    – DMGregory
    Oct 28, 2021 at 17:35
  • $\begingroup$ Thanks. Makes sense $\endgroup$
    – Akash KC
    Oct 28, 2021 at 18:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.