Activity Selection Problem

This problem can be solved using the Greedy Approach.

Goal: Given n activities with their start and finish times, find the maximum number of activities that a single person can perform, given that he/she can perform only one activity at a time.

For example:

ACTIVITY A1 A2 A3
START 12 10 20
FINISH 25 20 30

Solution: A2, A3

Algorithm:

  1. Sort the activities according to their finish times
  2. Print the first activity in the sorted array
  3. For the rest of the activities in the array: print the activity if its start time is greater than or equal to the finish time of the previous task

In the above example:

Sorting according to finish times:

ACTIVITY A2 A1 A3
START 10 12 20
FINISH 20 25 30

Now print A2.

Then, check if A1 has start time >= finish time of A2. It doesn't. So, check the same for A3.

Since A3 has start time >= finish time of A2, print A3.

Output: A2, A3

Time Complexity: O(n) for sorted input, O(nlgn) for unsorted input.

results matching ""

    No results matching ""