Find if entire range is covered up given a set of N intervals

Question

Suppose I have N intervals of the form [start,end]. I need to find out if an entire range is covered up by these intervals .

For eg: If my intervals are [4.5,5.765] and [5.8,10] and the interval is [5,10] it should report false where as for the same data if interval is [6,9.99] it should report true.

I need a precision of 1e-9.And intervals as well as range will be in [-1000,1000].

Is this problem solvable in O(NlgN) time ?? Where N=number of intervals .

Answer 1

If you sort the start and end points of all the intervals (O(N * log N)), then in an O(N) pass you can keep track of:

• the current position on the number line between -1000 and 1000, which in turn takes each start/end point of any interval.
• how many intervals are "currently" open, i.e. how many intervals intersect at this point on the number line.

If at any point in this pass, the current value is in the target range and the current number of intervals is 0, then the target range is not covered by the intervals. If that never happens before you reach the end of the target range, then the target is covered.

Since the intervals are closed, remember to sort an "end point" with value r before a "start point" with value r, to ensure that you return "true" for the case where the intervals are [0,1] and [1,2] and the target is [0,2].

IEEE double precision is sufficient for granularity 1e-9 on the range +/-1000, but do beware of the problem that 5.8 cannot be exactly represented in binary floating-point. So depending on how your intervals are calculated, there might be tiny "gaps" introduced by computation or representation errors. For this reason you might like to do some kind of rounding to the nearest billionth before you start, and/or use a base-10 rather than base-2 representation of the values involved.