Greedy Algorithm

Def Greedy Algorithm The greedy algorithm makes locally optimal choices and may lead to a globally optimal solution.

Fact Requirements of Greedy Algorithm

• Optimal Sub-Structure: Optimal solution to the problem is formed by optimal solutions to sub-problems.
• Greedy-Choice Property: A globally optimal solution can be formed from locally optimal solutions.

Fact Generally, greedy algorithms are faster than dynamic programmings.

Prop Any problem that can be solved by greedy can also be solved by dynamic programming.

Activity Selection Problem

Def Activity Selection Problem Consider a set of activities . Each activity takes place on the interval . And we call and are compatible if . Find the largest subset of consisting of mutually compatible activities.

Algorithm

1. Sort the activities based on the starting points, give
2. Sort the activities based on the finish points, give
3. Start with an empty set
4. While is not empty:
   1. Find the activity with the and add it to
   2. Remove any activity in which overlaps with using and
5. Return

Proof Consider a set of activities . Let such that . Claim that there exists an optimal solution such that . Suppose is some optimal solution. Let such that . Since , . Clearly if . Case , then exists which is also an optimal solution.

Prop The overall time complexity of the above algorithm is in .