Activity Selection Problem

Problem Statement

Given N activities with their start time and end time. The task is to find the solution set having a maximum number of non-conflicting activities that can be executed within the given time, assuming only a single activity can be performed at a given time.

Examples:

Input: start[] = [10, 12, 20}]         
          end[] =  [20, 25, 30]
Output: [0, 2]
Explanation: A maximum of two activities can be performed, i.e. Activity 0 and Activity 2[0-based indexing]. 

Input:  start[]  =  [1, 3, 0, 5, 8, 5]
finish[] =  [2, 4, 6, 7, 9, 9]
Output: [0, 1, 3, 4]
Explanation: A maximum of four activities can be performed, i.e. Activity 0, Activity 1, Activity 3, and Activity 4[0-based indexing]. 

Greedy Algorithm Method

The Activity selection problem can be solved using Greedy Approach. Our task is to maximize the number of non-conflicting activities.

Two activities A1 and A2 are said to be non-conflicting if S1 >= F2 or S2 >= F1, where S and F denote the start and end time respectively.

Since we need to maximize the maximum number of activities. The idea would be to choose the activity with the least finish time. Finishing the smallest activities would help adjust the remaining tasks.

Algorithm

• Sort the arrays according to their finish time, in case they are not sorted.
• Choose the first activity from the array and insert it into the sol array.
• If the start time of ith activity is greater than or equal to the finish time of the (i – 1)th activity, print the ith activity, since it is ready for execution.
• Repeat the above steps till the end of the array.

C++ Code For Greedy Algorith Method

void printMaxActivities(int s[], int f[], int n)
{
    int i, j;
 
    cout <<"Following activities are selected "<< endl;
    i = 0;
    cout <<" "<< i;
    for (j = 1; j < n; j++)
    {
      if (s[j] >= f[i])
      {
          cout <<" " << j;
          i = j;
      }
    }
}

Java Code For Greedy Algorith Method

public static void printMaxActivities(int s[], int f[], int n)
    {
    int i, j;
      
    System.out.print("Following activities are selected : n");
    i = 0;
    System.out.print(i+" ");
    for (j = 1; j < n; j++)
    {
         if (s[j] >= f[i])
         {
              System.out.print(j+" ");
              i = j;
          }
     }
    }

Python Code For Greedy Algorith Method

def printMaxActivities(s , f ):
    n = len(f)
    print "The following activities are selected"
    
    i = 0
    print(i, end=" ")
 
    for j in xrange(n):
        if s[j] >= f[i]:
            print(j,end=" ")
            i = j

Time Complexity:

• Case 1 : O(N), in case, the given array is sorted according to their finish times, where N is total steps.
• Case 2 : O(NlogN), in case, the given array is not sorted according to their finish times, where N is total steps.

Space Complexity:O(1), since no extra space is used.

Practice Question

Activity Selection Problem

Frequently Asked Questions

Which approach is more efficient for the Activity Selection Problem?
The Greedy algorithm approach is the best approach to solve this problem.

Is it necessary to sort the array if the given array is unsorted?
Yes, the array needs to be sorted in ascending order according to the finish time. This helps us greedily assign time to maximum items.