It's greedy~

Greedy can pass this problem quickly.

Re: It's greedy~

*Edited by author 11.11.2012 02:32*

Re: It's greedy~

Posted by

shafaet 30 Dec 2011 01:11

of course greedy is correct. First sort the data according to finish time,than starting time.

Re: It's greedy~

Why won't greedy pass? Exactly this problem is used to teach greedy in most of all text books(all I have ever read).

How are you applying greedy approach after sorting by finish time, then starting time?

Suppose I have sorted the data by finish time and then by start time. Now what are you doing with the data? Are you binary searching over the data for each of the N events of the array? Please specify more.

Re: How are you applying greedy approach after sorting by finish time, then starting time?

Posted by

nic 6 Nov 2013 20:15

one linear pass

Re: How are you applying greedy approach after sorting by finish time, then starting time?

Posted by

naik 4 Jun 2014 00:54

Useful test:

3

1 6

2 3

4 5

Answer: 2