Find a number closest to 0 that isn't taken by any of the intervals (set of two numbers indicating left and right value)

user_13440079 0
Viewed 83

I am not sure why I am stuck on this for so long. I basically have this setup. An range of possible values from -180 to 180. And a list of intervals in that range. I am looking for a number closest to 0 that isn't taken by any of the intervals. (If there is just one interval of [-13,22], I'd like to return -13, no need to return closest number that isn't -13. So the actual interval numbers are excluded, but everything between them is a no go.)

enter image description here

I am actually projecting circles (obstacles) onto navigation of my unit, and now I need to find the closest point to go towards.

The intervals would look something like [-40, -23], [-3, 16], [70, 93]...

Thank you! I hopefully explained my problem properly, it seems rather trivial but my brain just doesn't let me solve it.

math algorithm
2 Answers

First you need to merge your intervals to make sure that they don't overlap, for example if you have [1, 13] and [7, 21] you turn it into a single [1, 21] interval.

Then you go through all your intervals and find the one which includes 0, if you can't find one, then 0 is free and can be taken, otherwise choose the bound of the interval closer to 0.

user_32586980

Imagine representing your intervals as pairs of "events." For example, the interval [x, y] can be thought of as an event at time x where an interval opens and an event at time y where an interval closes.

Thinking of your intervals this way, convert your intervals into events and sort the events from left to right. Now, scan across the intervals from left to right, maintaining a counter that represents the number of intervals that you're currently in. Every time you pass an "interval open" event, increment the counter. Every time you pass an "interval close" event, decrement the counter.

Each time your counter switches from 0 to 1 or from 1 to 0, you've identified a boundary point of a window in which there are no open intervals - do you see why? You can therefore find the point closest to zero by taking the transition point closest to zero, or zero itself if it happens to be the case that as you're scanning from the left to the right you find that no intervals are active when you cross zero.

This can be done in time O(n log n) using a regular sorting algorithm like quicksort or heapsort, and potentially faster if you use an integer sorting algorithm.

user_5015570
Related