6

Suppose you are given a set of intervals, with the starting time of each interval as s subscript i and the finishing time of f subscript i. Find the minimum number of points that need to be placed to that every interval has a point.

I'm trying to find an algorithm that would solve this. I'm getting stuck when an interval that overlap two intervals, i.e starts halfway through one interval and ends halfway through another has an interval that is contained in it.

Thanks

4 Answers 4

10
  1. Remove any intervals that completely contain a smaller interval. You can do this because, if the smaller interval is satisfied, then the larger interval must also be satisfied.
  2. Sort intervals by s_i.
  3. Starting from the first interval: place a point at f_i. This will satisfy the first interval, and any intervals that overlap it.
  4. Continue in sorted order to the next interval that does not yet contain a point, and place a point at f_i.
  5. Repeat.
17
  • 1
    Just sort the intervals by f_i, then there's no need in the first step.
    – adamax
    Feb 10, 2011 at 21:09
  • Also note that because of the element distinctness problem, this algorithm is actually optimal: O(nlogn).
    – Aryabhatta
    Feb 10, 2011 at 22:31
  • 2
    @adam: It leaves some details, but it does provide an algorithm. The most obvious implementation is O(nlogn). Of course, if you wanted to, you could shoot yourself in the foot and use bogosort instead of heapsort etc.
    – Aryabhatta
    Feb 11, 2011 at 7:03
  • 1
    @Moron How would you implement the 1st step in O(n log n)? The obvious one is O(n^2). And with naive implementation of the 4th step you'll get O(n^2) as well.
    – adamax
    Feb 11, 2011 at 19:20
  • 1
    @adamax: Obvious != naive. The first step can be done in O(nlogn) time. Sort the left co-ords. Say the sorted order is s1, s2, .., sn. The right is f1, f2, ..., fn, which need not be sorted. For each i, binary search fi in the s1, s2, ..., sn. Say fi < s_j+1. Now we need to find the minimum in [fi+1, ..., fj]. This can be done in O(logn) time by maintaining a tree of the f_i (this is a well known problem called range minimum query and can in fact be done in O(1) time with O(n) preprocessing). Step 4 should be possible to do using binary search on the sorted arrays...
    – Aryabhatta
    Feb 11, 2011 at 19:39
7

This question needs an answer with code. Here is a python implementation of the algorithm that user612112 mentions, which is a little better than the one in the accepted answer:

  1. Initialize an empty list of output points
  2. Sort the ranges by end point, and process them in end point order
  3. For each range, if the last output point is less than the start of the range, then add the range's end point to the output set

Note that you don't need any preprocessing to remove redundant ranges, and you don't need the sort to distinguish between multiple ranges with the same end point.

# given some inclusive ranges
ranges=[(1,5),(2,4),(4,6),(3,7),(5,9),(6,6)]

# sort by the end points
ranges.sort(key=lambda p:p[1])

#generate required points
out=[]
last = None
for r in ranges:
    if last == None or last < r[0]:
        last = r[1]
        out.append(last)

#print answer
print(out)
1
  • 1
    Good solution. Runs in O(nlogn + n) time.
    – Sssssuppp
    Oct 27, 2019 at 15:55
5
  1. Sort the intervals in order of nondecreasing upper bound.
  2. Initialize a variable most_recent_placed to -inf (something less than all interval lower bounds).
  3. Scan the intervals in sorted order. For a given interval [a, b], if most_recent_placed < a, then put a point at b and set most_recent_placed to b.

The proof that this solution A is optimal is to establish inductively that for any valid solution B and any point x, the number of points placed by B with coordinates less than x is at least as large as the number of points placed by A left of x.

0

First sort the intervals in increasing order of starting point. put a point on the smallest fi. if the next interval which has finishing time f(i + 1) has this point then the previous point covers f(i+1) else put new point at f(i+1). Iterate the procedure

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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