Practice
Resources
Contests
Online IDE
New
Free Mock
Events New Scaler
Practice
Improve your coding skills with our resources
Contests
Compete in popular contests with top coders
Events
Attend free live masterclass hosted by top tech professionals
New
Scaler
Explore Offerings by SCALER

## Greedy Algorithm

Last Updated: Nov 17, 2023
Go to Problems
Greedy Algorithm
Complete all the problems in this Topic to unlock a badge
Completed
Go to Problems
Contents

# Activity Selection problem

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.

Example:

``````    Consider the following 6 activities.
start[]  =  {1, 3, 0, 5, 8, 5};
finish[] =  {2, 4, 6, 7, 9, 9};
The maximum set of activities that can be executed
by a single person is {0, 1, 3, 4}
``````

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 previously selected activity. We can sort the activities according to their finishing time so that we always consider the next activity as minimum finishing time activity.

1. Sort the activities according to their finishing time
2. Select the first activity from the sorted array and print it.
3. Do following for remaining activities in the sorted array.
…….a) If the start time of this activity is greater than the finish time of previously selected activity then select this activity and print it.

An example code to clarify it further :

``````        // Prints a maximum set of activities that can be done by a single
// person, one at a time.
//  n   -->  Total number of activities
//  s[] -->  An array that contains start time of all activities
//  f[] -->  An array that contains finish time of all activities ( sorted )
void printMaxActivities(int s[], int f[], int n)
{
int i, j;

printf ("Following activities are selected \n");

// The first activity always gets selected
i = 0;
printf("%d ", i);

// Consider rest of the activities
for (j = 1; j < n; j++)
{
// If this activity has start time greater than or equal to the finish
// time of previously selected activity, then select it
if (s[j] >= f[i])
{
printf ("%d ", j);
i = j;
}
}
}
``````

How does Greedy Choice work for Activities sorted according to finish time?

Let the give set of activities be `S = {1, 2, 3, ..n}` and activities be sorted by finish time. The greedy choice is to always pick activity 1. How come the activity 1 always provides one of the optimal solutions. We can prove it by showing that if there is another solution B with first activity other than 1, then there is also a solution A of same size with activity 1 as first activity. Let the first activity selected by B be k, then there always exist `A = {B – {k}} U {1}`.

(Note that the activities in B are independent and k has smallest finishing time among all. Since k is not 1, `finish(k) >= finish(1)`).

## Greedy Algorithm Problems

0/4
Easy Greedy
0/6
Medium Greedy
Topic Bonus
Bonus will be unlocked after solving min. 1 problem from each bucket

## Video Courses By

View All Courses
Excel at your interview with Masterclasses Know More
Certificate included
What will you Learn?
Free Mock Assessment
Fill up the details for personalised experience.
Phone Number *
OTP will be sent to this number for verification
+33 *
+33
Change Number
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
*Enter the expected year of graduation if you're student
Current Employer
Company Name
College/University Name
Job Title
Job Title
Software Development Engineer (Backend)
Software Development Engineer (Frontend)
Software Development Engineer (Full Stack)
Data Scientist
Android Engineer
iOS Engineer
Devops Engineer
Support Engineer
Research Engineer
Engineering Intern
QA Engineer
Co-founder
SDET
Product Manager
Product Designer
Backend Architect
Program Manager
Release Engineer