{"id":1362,"date":"2020-06-10T19:28:11","date_gmt":"2020-06-10T19:28:11","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1362"},"modified":"2022-03-28T00:26:38","modified_gmt":"2022-03-28T00:26:38","slug":"activity-selection-problem","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/activity-selection-problem\/","title":{"rendered":"ACTIVITY SELECTION PROBLEM"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Greedy algorithm.<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Medium.<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

PrepBuddy is given N activities with their start and finish times. The task is to select the maximum number of activities that can be performed by PrepBuddy, assuming that he can only work on a single activity at a time.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

For Example :<\/h4>\n
2\n5\n1 3 4 6 8\n3 5 13 14 15\n6\n3 5 6 7 8 9\n5 7 8 9 10 12\n\n3\n4\n\nIn the first test case, the activities present at index 0, 1 and 3 can be completed.\nIn the second test case, the activities present at index 0, 1, 3 and 4 can be completed.<\/code><\/pre>\n
OBSERVATION:<\/h3>\n
\n
Activity selection problem is one of the most frequently asked problems and also holds great significance when it comes to implementing greedy algorithm.<\/p>\n
The activity selection problem is a combinatorial optimization problem concerning the selection of non-conflicting activities to perform within a given time frame, given a set of activities each marked by a start time (si) and finish time (fi). The problem is to select the maximum number of activities that can be performed by a single person or machine, assuming that a person can only work on a single activity at a time. The activity selection problem is also known as the Interval scheduling maximization problem (ISMP), which is a special type of the more general Interval Scheduling problem.<\/p>\n<\/blockquote>\n
SOLVING APPROACH:<\/h3>\n
What does greedy say???<\/em><\/strong><\/p>\n
\n
It says that, at every step, we can make a choice that looks best at the moment, and we get the optimal solution of the complete problem.<\/p>\n
Here,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. <\/p>\n
We can sort the activities according to their finishing time so that we always consider the next activity as minimum finishing time activity.<\/p>\n<\/blockquote>\n
    \n
  1. \n
    Sort the activities according to their finish time.<\/p>\n<\/li>\n
  2. \n
    Select the first activity and set the counter to 1.<\/p>\n<\/li>\n
  3. \n
    Now iterate over the entire array and keep comparing the selected finish time with the current start time.<\/p>\n<\/li>\n
  4. \n
    If the start time is greater ,increment the counter by 1 and change the value of the selected finish time to the current finish time.<\/p>\n<\/li>\n<\/ol>\n
    \n
    Time Complexity:<\/strong>
    \nWhen activities are sorted by their finish time: O(N)
    \nWhen activities are not sorted by their finish time, the time complexity is O(N log N) due to complexity of sorting.<\/p>\n<\/blockquote>\n
    SOLUTIONS:<\/h3>\n
    \t\t\t\t\t\t