Interval selection algorithm

Question

Let's say we have a set of intervals [s1,e1],[s2,e2]...[sn,en]

I would like to find the subset of non-overlapping intervals and has the maximum aggregate time.

Actually I'm looking for a greedy solution. Does it exist or not?

This is not too hard using dynamic programming. Hint: how much can you aggregate until each en? — John Dvorak
– John Dvorak, Commented Jul 7, 2013 at 19:59
This is a very common problem indeed. Are you sure you have tried enough? — Fallen
– Fallen, Commented Jul 7, 2013 at 20:00
possible duplicate of Algorithm to find the maximum sum in a sequence of overlapping intervals — David Eisenstat
– David Eisenstat, Commented Jul 7, 2013 at 20:05
See the duplicate. Since the uniqueness problem is a subproblem for this, there is no algorithm better than th(n log n). — John Dvorak
– John Dvorak, Commented Jul 7, 2013 at 20:27

David Eisenstat · Accepted Answer · 2013-07-07 20:54:50Z

1

"Greedy" is not a formal term, but for the purpose of this question, let's define the class of greedy algorithms to be those that impose an a priori total order on intervals (i.e., independent of the input) and repeatedly extend the partial solution by the maximum available interval. Consider the inputs

[0,2],[1,4],[3,5]
[0,2],[1,4]
[1,4],[3,5].

There are three possibilities for the maximum interval among [0,2],[1,4],[3,5]. If [0,2] or [3,5] is maximum, then the greedy algorithm answers incorrectly for the second or third input respectively. If [1,4] is maximum, then the greedy algorithm answers incorrectly for the first input.

answered Jul 7, 2013 at 20:54

David Eisenstat

65.7k7 gold badges66 silver badges127 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

Fallen Over a year ago

An O(N^2) greedy approach will work for these 3 inputs. like, for first case, we'll start taking the first interval [0,2] then ignore 2nd (because it intersects with [0,2]) and take the 3rd. at the next step we'll take the second and compare and we'll get that the [0,2]+[3,5] interval is the best For the 2nd input, we'll start with [0,2]. It intersects with [1,4]. So again we start with [1,4]. And we find that the best is [1,4]. Same for the 3rd input. but this time we'll find that the first one is better. There is no greedy solution for this problem but these cases seem to be weak.

David Eisenstat Over a year ago

@MuhammedHedayet That's not a "greedy" algorithm. I have no idea what greedy means for you and thus no idea why you're so sure that no greedy algorithm exists.

Fallen Over a year ago

why that's not greedy? :) I'm starting from any interval and choosing the next interval greedily such that the next interval doesn't intersect with the previous one. A greedy algorithm always makes the choice that looks best at the moment I hope this answers why no greedy algorithm exists for this particular problem :)

David Eisenstat Over a year ago

@MuhammedHedayet It's not a greedy algorithm by my definition, and yours isn't formal.

Fallen Over a year ago

My one is copied from CLRS :) Still you believe it's not formal? ;-)

|

Collectives™ on Stack Overflow

Interval selection algorithm

1 Answer 1

8 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

8 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related