CODEWITHSUNDEEP
algorithm
Jun
Jun

Reputation: 426

Interval selection algorithm

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?

Upvotes: 0

Views: 1163

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65447

"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.

Upvotes: 1

Related Questions