Activity Selection
Problem
TEST TIME ON KRUSKAL'S
ALGORITHM
URL:
[Link]
QR CODE:
GREEDY ALGORITHMS
Introduction
A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally
optimal choice at each stage
In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic
can yield locally optimal solutions that approximate a globally optimal solution in a reasonable
amount of time.
Example: In Travelling Sales Problem, the heuristic is "At each step of the journey, visit the
nearest unvisited city."
This problem has unreasonably many steps and greedy approach limits them
GREEDY ALGORITHMS
Example
Greedy algorithms determine the minimum
number of coins to give while making change.
The image represents the steps most people
would take to emulate a greedy algorithm to
represent 36 cents using only coins with values
{1, 5, 10, 20}.
The coin of the highest value, less than the
remaining change owed, is the local optimum.
GREEDY ALGORITHMS
Properties
Greedy Algorithm solves problems by making the best choice that seems best at the
particular moment.
A greedy algorithm works if a problem exhibits the following two properties:
1. Greedy Choice Property: A globally optimal solution can be reached at by
creating a locally optimal solution. In other words, an optimal solution can be
obtained by creating "greedy" choices.
2. Optimal substructure: Optimal solutions contain optimal subsolutions. In other
words, answers to subproblems of an optimal solution are optimal.
ACTIVITY SELECTION PROBLEM
Introduction
Recap: At every step, we can make a choice that looks best at the
moment, and we get the optimal solution of the complete problem.
Activity Selection Problem is a fine example of a Greedy Algorithm
Problem Statement: You are given n activities with their start and finish
times. Select the maximum number of activities that can be performed by
a single person, assuming that a person can only work on a single activity
at a time.
ACTIVITY SELECTION PROBLEM
Introduction
Recap: At every step, we can make a choice that looks best at the
moment, and we get the optimal solution of the complete problem.
Activity Selection Problem is a fine example of a Greedy Algorithm
Problem Statement: You are given n activities with their start and finish
times. Select the maximum number of activities that can be performed by
a single person, assuming that a person can only work on a single activity
at a time.
ACTIVITY SELECTION PROBLEM
Examples
Consider the following examples
Input Input
start[] = {10, 12, 20}; start[] = {1, 3, 0, 5, 8, 5};
finish[] = {20, 25, 30}; finish[] = {2, 4, 6, 7, 9, 9};
Output Output
{0,2} {0, 1, 3, 4}
Explanation Explanation
A person can perform at most two A person can perform at most four
activities. The maximum set of activities activities. The maximum set of activities
that can be executed is {0, 2} that can be executed is {0, 1, 3, 4}
These are indexes in start[] and finish[]
ACTIVITY SELECTION PROBLEM
Algorithm
The greedy choice is to always pick the next activity whose finish time is
least among the remaining activities and the start time is more than or
equal to the finish time of the previously selected activity.
1) Sort the activities according to their finishing time
2) Select the first activity from the sorted array and print it.
3) Do the following for the remaining activities in the sorted array.
If the start time of this activity is greater than or equal to the finish
time of the previously selected activity then select this activity and print it.
ACTIVITY SELECTION
PROBLEM
ACTIVITY SELECTION PROBLEM
Program
Activities are sorted here
Sample IO
Input
start = {1, 3, 0, 5, 8, 5};
end = {2, 4, 6, 7, 9, 9};
Output
0134
Time Complexity: O(n)
ACTIVITY SELECTION PROBLEM
import [Link].*; [Link](j + " ");
import [Link].*; i = j;
import [Link].*; }}
class ActivitySelection { }
public static void printMaxActivities(int public static void main(String[] args)
s[], int f[],int n) { {
int i, j; int s[] = { 1, 3, 0, 5, 8, 5 };
[Link]( int f[] = { 2, 4, 6, 7, 9, 9 };
"Following activities are selected"); int n = [Link];
i = 0; printMaxActivities(s, f,
[Link](i + " "); n);
for (j = 1; j < n; j++) { }
if (s[j] >= f[i]) { }
THANK
YOU
+91 78150 codemithra@[Link] [Link]
95095