Given a set of ranges S, and an overlapping range

问题:

The following is a practice interview question that was given to me by someone, and I'm not sure what the best solution to this is:

Given a set of ranges:
(e.g. S = {(1, 4), (30, 40), (20, 91) ,(8, 10), (6, 7), (3, 9), (9, 12), (11, 14)}. And given a target range R (e.g. R = (3, 13) - meaning the range going from 3 to 13). Write an algorithm to find the smallest set of ranges that covers your target range. All of the ranges in the set must overlap in order to be considered as spanning the entire target range. (In this example, the answer would be {(3, 9), (9, 12), (11, 14)}.

What is the best way to solve this? I was thinking this would be done using a greedy algorithm. In our example above, we would look for all of the numbers that intersect with 3, and pick from those the one with the highest max. Then we would do the same thing with the one we just picked. So, since we picked (3, 9) we now want to find all of the ranges that intersect 9, and among those, we pick the one with the highest max. In that iteration, we picked (9, 12). We do the same thing to that one, and we find that the next range that intersects 12, with the highest max is (11, 14).

After that iteration, we see that 14 is greater than 13 (the max of our range), so we can stop.

The problem I'm having with this algorithm is, how do efficiently query the intersecting ranges? If we try a linear search, we end up with an algorithm that is O(n^2). My next thought was to cross off any of our intersecting ranges from our list each time we run through the loop. So in the first iteration, we cross of (1, 4) and (3, 9). In our next iteration we cross of (9, 12), (3, 9), and (8, 10). So by the last iteration, all we have to look through is {(30, 40), (20, 91), (6, 7)}. We could make this even more efficient by also crossing out everything that has a min > 13, and a max < 3. The problem is this still might not be enough. There is still the potential problem of having lots of duplicate sequences within the bounds of our range. If our list of ranges contained something like {(6, 7), (6, 7), (6, 7), (6, 7), (6, 7)} we would have to look through those each time, even though they aren't useful to us. Even if we were only to store unique values (by putting them all in a set), we might have a really big range, with a bunch of ranges that are inside of our target range, but we also have one range inside that spans almost the entire target range.

What would be an efficient way to query our ranges? Or possibly, what would be a more efficient algorithm to solving this problem?

回答1:

How about using an interval tree for queries? (https://en.m.wikipedia.org/wiki/Interval_tree) I'm not sure if greedy could work here or not. If we look at the last set of choices, overlapping with the high point in R, there's a possibility of overlap between the earlier choices for each one of those, for example:

R = (2,10) and we have (8,10) and (7,10) both overlapping with (6,8)

In that case, we only need to store one value for (6,8) as a second leg of the path; and visiting (6,8) again as we make longer paths towards the low point in R would be superfluous since we already know (6,8) was visited with a lower leg count. So your idea of eliminating intervals as we go makes sense. Could something like this work?

leg = 1
start with the possible end (or beginning) intervals
label these intervals with leg
until end of path is reached:
  remove the intervals labeled leg from the tree
  for each of those intervals labeled leg:
    list overlapping intervals in the chosen direction
  leg = leg + 1
  label the listed overlapping intervals with leg

回答2:

I can suggest following algorithm with complexity O(n log n) without using Intervals trees.

Let introduce some notation. We should cover a range (X,Y) by intervals (x_i,y_i).

First sort given intervals (x_i,y_i) by start point. It will take O(n log n)

Let select from intervals (x_i,y_i) with x_i <= X interval (x_k,y_k) with maximum of y_i. Because interval already sorted by start point, we can just increment index, while interval satisfies condition. If y_k less than X, there are no solution for given set and range. In other case interval (x_k,y_k) contains 'X' and has maximal end point among intervals containing X.

Now we need to cover an interval (y_k, Y), to satisfy overlapping condition. Because for all intervals containing X has end point less than y_k+1, we can start from last interval from the previous step.

Each interval was used only once in this stage, so the time complexity of this part is O(n) and in total O(n log n).

Following code snippet for solution:

intervals // given intervals from set S
(X, Y) // range to cover
sort intervals 
i = 0 // start index
start = X // start point
result_set // set to store result
while start <= Y && i < len(intervals): 
   next_start =  intervals[i].y
   to_add = intervals[i]
   while intervals[i].x <= start && i < len(intervals):
        if next_start > intervals[i].y:
           next_start = intervals[i].y
           to_add = intervals[i]
        i++
   if(next_start < start):
        print 'No solution'
        exit
   start = next_start
   result_set add to_add

回答3:

Ok, after trying a bunch of different things, here is my solution. It runs in O(nlogn) time, and doesn't require the use of an Interval Tree (although I would probably use it if I could memorize how to implement one for an interview, but I think that would take too long without providing any real benefit).

The bottleneck of this algorithm is in the sorting. Every item is only touched once, but it only works with a sorted array, so that is the first thing we do. Thus the O(nlogn) time complexity. Because it modifies the original array , it has an O(1) space complexity, but if we were not allowed to modify the original array, we can just make a copy of it, and keep the rest of the algorithm the same, making the space complexity O(n).

import java.util.*;

class SmallestRangingSet {
    static class Interval implements Comparable<Interval>{
        Integer min;
        Integer max;
        public Interval(int min, int max) {
            this.min = min;
            this.max = max;
        }

        boolean intersects(int num) {
            return (min <= num && max >= num);
        }

        //Overrides the compareTo method so it will be sorted
        //in order relative to the min value
        @Override
        public int compareTo(Interval obj) {
            if (min > obj.min) return 1;
            else if (min < obj.min) return -1;
            else return 0;
        }
    }

    public static Set<Interval> smallestIntervalSet(Interval[] set, Interval target) {
        //Bottleneck is here. The array is sorted, giving this algorithm O(nlogn) time
        Arrays.sort(set);

        //Create a set to store our ranges in
        Set<Interval> smallSet = new HashSet<Interval>();
        //Create a variable to keep track of the most optimal range, relative
        //to the range before it, at all times.
        Interval bestOfCurr = null;
        //Keep track of the specific number that any given range will need to
        //intersect with. Initialize it to the target-min-value.
        int currBestNum = target.min;
        //Go through each element in our sorted array.
        for (int i = 0; i < set.length; i++) {
            Interval currInterval = set[i];
            //If we have already passed our target max, break.
            if (currBestNum >= target.max)
                break;
            //Otherwise, if the current interval intersects with
            //our currBestNum
            if (currInterval.intersects(currBestNum)) {
                //If the current interval, which intersects currBestNum
                //has a greater max, then our current bestOfCurr
                //Update bestOfCurr to be equal to currInterval.
                if (bestOfCurr == null || currInterval.max >= bestOfCurr.max) {
                    bestOfCurr = currInterval;
                }
            }
            //If our range does not intersect, we can assume that the most recently
            //updated bestOfCurr is probably the most optimal new range to add to 
            //our set. However, if bestOfCurr is null, it means it was never updated,
            //because there is a gap somewhere when trying to fill our target range.
            //So we must check for null first.
            else if (bestOfCurr != null) {
                //If it's not null, add bestOfCurr to our set
                smallSet.add(bestOfCurr);
                //Update currBestNum to look for intervals that
                //intersect with bestOfCurr.max
                currBestNum = bestOfCurr.max;
                //This line is here because without it, it actually skips over
                //the next Interval, which is problematic if your sorted array
                //has two optimal Intervals next to eachother.
                i--;
                //set bestOfCurr to null, so that it won't run
                //this section of code twice on the same Interval.
                bestOfCurr = null;
            }

        }

        //Now we should just make sure that we have in fact covered the entire
        //target range. If we haven't, then we are going to return an empty list.
        if (currBestNum < target.max)
            smallSet.clear();
        return smallSet;
    }

    public static void main(String[] args) {
        //{(1, 4), (30, 40), (20, 91) ,(8, 10), (6, 7), (3, 9), (9, 12), (11, 14)}
        Interval[] interv = {
                new Interval(1, 4),
                new Interval(30, 40),
                new Interval(20, 91),
                new Interval(8, 10),
                new Interval(6, 7),
                new Interval(3, 9),
                new Interval(9, 12),
                new Interval(11, 14)
        };
        Set<Interval> newSet = smallestIntervalSet(interv, new Interval(3,14));
        for (Interval intrv : newSet) {
            System.out.print("(" + intrv.min + ", " + intrv.max + ") ");
        }

    }
}

Output

(3, 9) (9, 12) (11, 14)

回答4:

Your assignment intrigued me, so I wrote a C++ program that solves the problem by iterating through the ranges that overlap the left side of the target range, and recursively searches for the smallest number of ranges that covers the remaining (right side) of the target range.

A significant optimization to this algorithm (not shown in this program) would be to, for each recursive level, use the range that overlaps the left side of the target range by the largest amount, and discarding from further consideration all ranges that overlap the left side by smaller amounts. By employing this rule, I believe there would be at most a single descent into the recursive call tree. Such an optimization would produce an algorithm having complexity O(n log(n)). (n to account for the depth of recursion, and log(n) to account for the binary search to find the range having the most overlap.)

This program produces the following as output:

{ (3, 9) (9, 12) (11, 14) }

Here is the program:

#include <utility>  // for std::pair
#include <vector>   // for std::vector
#include <iostream> // for std::cout & std::endl

typedef std::pair<int, int> range;
typedef std::vector<range> rangelist;

// function declarations
rangelist findRanges (range targetRange, rangelist candidateRanges);
void print (rangelist list);


int main()
{
    range target_range = { 3, 13 };

    rangelist candidate_ranges =
        { { 1, 4 }, { 30, 40 }, { 20, 91 }, { 8, 10 }, { 6, 7 }, { 3, 9 }, { 9, 12 }, { 11, 14 } };

    rangelist result = findRanges (target_range, candidate_ranges);

    print (result);
    return 0;
}


// Recursive function that returns the smallest subset of candidateRanges that
// covers the given targetRange.
// If there is no subset that covers the targetRange, then this function
// returns an empty rangelist.
//
rangelist findRanges (range targetRange, rangelist candidateRanges)
{
    rangelist::iterator it;
    rangelist smallest_list_so_far;

    for (it = candidateRanges.begin (); it != candidateRanges.end (); ++it) {

        // if this candidate range overlaps the beginning of the target range
        if (it->first <= targetRange.first && it->second >= targetRange.first) {

            // if this candidate range also overlaps the end of the target range
            if (it->second >= targetRange.second) {

                // done with this level - return a list of ranges consisting only of
                // this single candidate range
                return { *it };
            }
            else {
                // prepare new version of targetRange that excludes the subrange
                // overlapped by the present range
                range newTargetRange = { it->second + 1, targetRange.second };

                // prepare new version of candidateRanges that excludes the present range
                // from the list of ranges
                rangelist newCandidateRanges;
                rangelist::iterator it2;
                // copy all ranges up to but not including the present range
                for (it2 = candidateRanges.begin (); it2 != it; ++it2) {
                    newCandidateRanges.push_back (*it2);
                }
                // skip the present range
                it2++;
                // copy the remainder of ranges in the list
                for (; it2 != candidateRanges.end(); ++it2) {
                        newCandidateRanges.push_back (*it2);
                }

                // recursive call to find the smallest list of ranges that cover the remainder
                // of the target range not covered by the present range
                rangelist subList = findRanges (newTargetRange, newCandidateRanges);

                if (subList.size () == 0) {
                    // no solution includes the present range
                    continue;
                }
                else if (smallest_list_so_far.size () == 0 ||               // - first subList that covers the remainder of the target range
                         subList.size () < smallest_list_so_far.size ())    // - this subList is smaller than all previous ones checked
                {
                    // add the present range to the subList, which represents a solution
                    // (though possibly not optimal yet) at the present level of recursion
                    subList.push_back (*it);
                    smallest_list_so_far = subList;
                }
            }
        }
    }
    return smallest_list_so_far;
}

// print list of ranges
void print (rangelist list)
{
    rangelist::reverse_iterator rit;
    std::cout << "{ ";
    for (rit = list.rbegin (); rit != list.rend (); ++rit) {
        std::cout << "(" << rit->first << ", " << rit->second << ") ";
    }
    std::cout << "}" << std::endl;
}