Greedy algorithm

[calvinfornia]

Hi! Here's a problem about greedy algorithm.

The statement is below :
Suppose we have a set S = {a1, a2,...,an} of n proposed activities that wish to use a resource.
Each activity ai has a start time si and a finish time fi, where 0<= si < fi < ∞.
Activities ai and aj are compatible if the intervals [si,fi) and [sj,fj) do not overlap.
And the goal is to select a maximum size of mutually compatible activities.

There is a greedy algorithm solution to this problem by always choosing the compatible activity with the earliest finish time.

So, the question is, can it be modified to always choosing the compatible activity with the earliest "start" time? And what is the difference between two cases?

Thx in advance !

ps The problem is similar to this below link
https://www.geeksforgeeks.org/activity-selection-problem-greedy-algo-1/

[jonnin]

yes, you can do it that way.
it just changes the solution accordingly... the original gives you a set where they are chosen off the finish and the modification gives them chosen off the start.

greedy algorithm is a type of algorithm, not any one thing. It just means your algorithm makes a choice based off a condition that you set rather than attempt to choose the 'best' answer each time, it just grabs the one that meets the condition and keeps going.

another way to do it is to sort the set by the amount of time the process will take and select the shortest duration job that has no conflict each time. You can also set complex criteria, like the shortest duration and earliest start time, etc.

you can also double down. you can run multiple greedy algorithms and take the best answer from the set of those. This works really well for the travelling salesman problem: run the greedy algorithm starting at each node, and take the best of the set is usually a very good answer. This is wall-clock-time efficient on modern computers that have multiple CPUs and it can do them all in about the same time that it can do one, up to # of cores you have available...