CODEWITHSUNDEEP
algorithmmath
Varun Madiath
Varun Madiath

Reputation: 3242

Given a set of intervals, find the minimum number of points that need to be placed, so that every interval has a point in it

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

Upvotes: 6

Views: 8690

Answers (4)

Matt Timmermans
Matt Timmermans

Reputation: 59323

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)

Upvotes: 7

shmsi
shmsi

Reputation: 1088

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

Upvotes: 0

user612112
user612112

Reputation: 51

  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.

Upvotes: 5

mbeckish
mbeckish

Reputation: 10579

  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.

Upvotes: 10

Related Questions