CODEWITHSUNDEEP
algorithmrange
Wayne Rooney
Wayne Rooney

Reputation: 1607

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

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 .

Upvotes: 4

Views: 2895

Answers (3)

Ankush
Ankush

Reputation: 2554

You can do fuzzy sorting. The best case is O(n) and average case O(n log n). This is similar to quick sort. Best case happens when at least one point exists in all the the intervals, i.e. they all overlap. In general the more the overlap, better the algorithm wrt any other sorting algorithm.

Here is a detailed analysis for this algorithm. http://web.media.mit.edu/~dlanman/courses/cs157/HW3.pdf

Upvotes: 0

João Mendes
João Mendes

Reputation: 1425

While you've already gotten some good answers, I thought I'd contribute something plain and simple.

You haven't told us whether the intervals can overlap, so I'm going to assume they can. (Otherwise, a simple O(N) search pass will tell you whether your range is within one of the intervals, or not.)

If the set of intervals will remain constant for multiple ranges, your best bet is to pre-sort the intervals according to their starting point. (This is usually an O(N logN) operation, but you only have to do it once). Then, you can do:

checkRange(range, intervals[])
    for each ( intv in intervals )
        if intv.start > range.start
            return false
        if intv.end >= range.end
            return true
        if intv.end > range.start
            range.start = interval.end

    return false

This is just the one O(N) pass.

If the set of intervals can change for each range, then the following recursive algorythm may or may not perform better than sorting the intervals every time:

delta = 1e-9

checkRange(range, intervals[])
    for each ( intv in intervals )
        if intv.start <= range.start and intv.end >= range.end
            return true
        if intv.end < range.start or intv.start > range.end
            continue
        if intv.start < range.start and intv.end > range.start
            range.start = interval.end
            continue
        if intv.start < range.end and intv.end > range.end
            range.start = interval.end
            continue
        range1 = new range(start = range.start, end = intv.start - delta)
        range2 = new range(start = intv.end + delta, end = range.end)
        intervals = intervals after intv
        return checkRange(range1, intervals) and checkRange(range2, intervals)

Because, for arrays or linked lists, you can keep intervals after intv in the same memory space as the original intervals[], this just uses some stack space for the recursive iterations and no more than that. As for the computational complexity, someone better than me will have to look into proving stuff about it, but I have a feeling it's probably quite decent.

Upvotes: 1

Steve Jessop
Steve Jessop

Reputation: 279255

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.

Upvotes: 2

Related Questions