2
$\begingroup$

I have been studying about activity-selection-problem and the solution of greedy choice I came across is to select the activity that finishes in the earliest among the present activities.

But surely there are other greedy choices to solve the problem. The one I have been able to figure out is to select the activity that starts last.

My question is: are there any other greedy choices that can lead to solve activity selection problem? Any formal proof is also appreciated.

$\endgroup$
  • $\begingroup$ Cf. Borodin's models of priority algorithms. $\endgroup$ – Yuval Filmus Sep 15 '13 at 4:06
  • $\begingroup$ Have you tried proving optimality of your criterion? $\endgroup$ – Raphael Sep 16 '13 at 7:59
  • $\begingroup$ Both the approaches work optimally. I could prove them. $\endgroup$ – Ravi Teja Sep 18 '13 at 12:13
  • $\begingroup$ OP means "to select the activity that starts last", moving back in time after that. The usual greedy algorithm on this problem is to select the activity that finishes the earliest, moving ahead in time after that. These two methods are essentially the same as they are symmetric to each other. $\endgroup$ – Apass.Jack Nov 21 '18 at 21:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.