Greedy Solution to Activity Selection Problem.

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.

You cannot perform the activity before it starts. The start and end times for each activity are fixed. This is different from the Job selection problem where each activity takes unit time and can be picked at any time before the deadline.

Example 1 : If there are 3 activities as below (StartTime, FinshTime):
     { (2,5), (1, 10), (5, 8) };
     The first activity starts at time-2 and finish at time-5.Second Activity start at time-3 and finist at 7 and the 3rd activity start at 5 and finish at 8.

If 2nd activity is picked then the first and third cannot be picked. But 1st and 3rd can be completed by the same person (because they are not overlaping).

Note that we are not trying to optimize the performance, we are just trying to complete maximum number of activities. For example, in the above example, the person will be busy from Time 1 to 10 if he picks up the second activity.

If the following activities are given.

Then we can pick a maximum of 4 activities (A1, A3, A4, A6). Because they are not overlapping with each other.

Solution:

We can use the following Greedy Algorithm to solve this problem:

1. Sort all the activities in ascending order on their finishing time.
2. Select the first activity and print it (It will be picked).
3. Iterate all the activities starting from the 2nd activity and do the following:
   1. If start time of current activity is greater than or equal to the finish time of last picked (selected) activity then pick this activity and print it, else drop the activity and move to the next activity.

Basically, we want to pick a non-conflicting activity that finishes at the earliest, so that it the chances of conflict with the next activity is minimum.

Java Code:

class ActivitySelection 
{ 
   class Activity
   {
      int start;
      int end;
      String name;
   }
   public static void printMaxActivities(Activity arr[], int n) 
   { 
      // IMPLEMENT THIS FUNCTION TO SORT THE ARRAY ON arr.end.
      quickSort(arr);
       
      // SELECT FIRST ACTIVITY 
      System.out.print(arr[0].name + " "); 
       
      int prev = 0; // PREV SELECTED ACTIVITY
      for(int cur = 1; cur < n; cur++) 
      { 
         if (a[cur].start >= a[prev].end) 
         { 
              System.out.print(a[cur].name + " "); 
              prev = cur; 
          } 
      } 
   } 
}

We  need to define the quickSort function that will take an array and sort it on the end field.

Time Complexity:

The function will take O(n) time. But because we are also sorting the array, the sorting will take O(n.lg(n)) time.

The activity selection problem can be used in scheduling multiple competing events in a room, such that each event has its own start and end time. It can also be used in scheduling the manufacturing of multiple products on the same machine, such that each product has its own production timelines.