FOR FREE CONTENT
Activity selection (Greedy Algorithm)
Back to ProgrammingDescription
Overview:
Activity scheduling problem:Given a set of activities N to be processed on a machine where each activity i ∈ N has a start time siand finish time fi. Two activities i and jare said to be non-conflicting if si ≥ fj or sj ≥ fi. The objective is to find a set of maximum number of non-conflicting activities. This problem is also known as Interval scheduling maximization problem (ISMP).
Greedy Algorithm: An algorithm paradigm that generates a solution by selecting local optimal solutions at each step i.e. it selects the best alternative solution at each step.
Greedy Approach to Activity Scheduling problem: The set of activities are sorted in ascending order of their finishing time. The first activity is selected (a greedy choice) and for each remaining activity, if it is non-conflicting with the previously selected activity, then it is selected.
Procedure:
Consider the following set of activities and their start time and finish time in the table below,
Next, the activities are sorted in ascending order of their finishing time as shown below.
The first activity is always selected, hence, a1 is selected. a2 and a5 are both conflicting with a1 as s2 ≤ f1 (or 4 ≤ 5) and s5 ≤ f1 (or 3 ≤ 5) where s2, s5 is the start time of a2 and a5 respectively and is the finish time of a1. Hence, a2, a5 are not selected. We proceed to the next activity, a4 which is non-conflicting with a1 as s4 ≥ f1 (or 6 ≥ 5). Hence, a4 is selected. The remaining activities a3, a6 are both conflicting with the previously selected activity a4 as s3 ≤ f4 (or 5 ≤ 12) and s6 ≤ f4 (or 9 ≤ 12). Hence, the final selected activities are a1, a4.
Algorithm
Algorithm:
Input:
1. An array of Activities consisting of Activity ID, Start Time & Finish Time.
Output:
1. Displays the Activity IDs of the selected Activities
Algo:
Step 1: Start
Step 2: Define user defined structure Activity with activityID, startTime & finishTime
Step 3: Defining the Input Activity function
void inputActivity (struct Activity activity[], int activitySize)
for i = 0 to i < activitySize repeat
Display “Input for Activity ” (i+1)
Display “Enter Activity ID”
Read activity[i].activityID
Display “Enter Activity Start Time”
Read activity[i].startTime
Display “Enter Activity Finish Time”
Read activity[i].finishTime
Step 4: Defining the Sort function
void sort(struct Activity activity[], int activitySize)
for i = 0 to i < activitySize repeat
Set flag 0
for j = 0 to j < (activitySize-i-1) repeat
Check if(activity[j+1].finishTime < activity[j].finishTime)
Set temp activity[j+1]
Set activity[j+1] activity[j]
Set activity[j] temp
Set flag 1
Check if(flag == 0)
break
Step 5: Defining selectActivity function
void selectActivity(struct Activity activity[], int activitySize, int result[])
Set result[0] 0
for i = 0 to i < activitySize repeat
Set result[i] -1
Set i 0
for j = 1 to j < activitySize repeat
check if(activity[j].startTime > activity[i].finishTime)
Set result[j] j
Set i j
Step 6: Defining displaySelectedActivity function
void displaySelectedActivity(struct Activity activity[], int activitySize, int result[])
for i = 0 to i < activitySize repeat
Check if(result[i] ≠ -1)
Display activity[result[i]].activityID
Step 7: Defining Main function
Display “Enter Activity Size”
Read activitySize
Set Activity activity[activitySize] Null
Set int result[activitySize] Null
Call inputActivity(activity, activitySize);
Call sort(activity, activitySize);
Call selectActivity(activity, activitySize, result);
Call displaySelectedActivity(activity, activitySize, result);
Step 8: Stop
Code
Characteristics of Activity selection problem:
● It requires the activities to be sorted in ascending order of finish time.
● The algorithm follows greedy algorithm paradigm
● It requires an extra space for storing the selected activities and hence, its space complexity is O(n) where n is the size of the array in which it is stored.
Activity Selection Problem Application:
● Scheduling a room for multipleevents in a competition, each having its own time requirements (start and finish time).
● Activity Selection problem finds its application in the field of Operation Research.
Activity Selection Problem Advantage:
● The solution to the Activity scheduling problem follows a greedy algorithm paradigm which makes it easier to implement than other paradigms such as dynamic programming or divide and conquer.
● If the activities are sorted in ascending order of their finishing time, the algorithm takes only O(n) time.
Activity Selection Problem Disadvantage:
● The activities must be sorted in ascending order of their finish time.
● If the activities are not sorted, the algorithm takes either O(n2) time or O(nlogn) time depending on the sorting algorithm.
Complexity:
Time Complexity of Activity Selection Problem:
(1) If the activities are sorted in ascending order of their finish time, the modified bubble sort function sort() takes O(n) time. In the selectActivity() function, we iterate each activity which takes O(n) time and comparison for non-conflicting activity takes O(1) time. Hence, the total time complexity if the activities are sorted is O(n).
(2) If the activities are not sorted, the sort() function takes O(n2) time. The complexity of the selectActivity() function is the same as in point (1). Hence, the total time complexity is O(n2) + O(n) = O(n2). This can be further optimized by using quicksort or heap sort instead of bubble sort which takes O(nlogn) time.
Space Complexity of Activity Selection Problem:
The selected activities’s indexes are stored in the result array which is the extra space required in the algorithm. Hence, the space complexity is O(n) where n is the size of the array in which it is stored.
