Activity Selection Problem

We are given N activities with their start time and finish time. Our task is to find the maximum number of non-conflicting activities that can be performed within a given time assuming that only a single activity can be performed at a time.

Scope

In this article we are looking upon Activity selection problem.

In this article we will learn constrins of activity selection problem.

In this article we will different approch of solving activity selection problem.

Takeaways

Time and Space Complexity for the Greedy approach when the given set of activities are not sorted is O(nlogn) and O(1)

Example of Activity Selection Problem

Input:
    N = 3
    arr[] = {{10, 20}, {12, 25}, {20, 30}}
Output:
    (10, 20) (20, 30)

Input:
    N = 4
    arr[] = {{3, 4}, {2, 5}, {1, 3}, {5, 9}, {0, 7}, {11, 12}, {8, 10}}
Output: 
    (1, 3) (3, 4) (5, 9) (11, 12)

Example Explanation

Suppose we are given the following 7 activities:

    arr[] = {{3, 4}, {2, 5}, {1, 3}, {5, 9}, {0, 7}, {11, 12}, {8, 10}}

Let us create 2 different arrays for start and finish time and sort them by finish time for better understanding:

    start[] = {1, 3, 2, 0, 5, 8, 11}
    finish[] = {3, 4, 5, 7, 9, 10, 12}

Since these activities are already sorted by their finish time, firstly the activity0 gets selected. As the start time of activity1 is equal to the finish time of activity0, it will also get selected. activity2 and activity3 are having smaller start times as compared to the finish time of activity1, so both these activities will get rejected.

Similarly activity4 and activity6 are also selected, whereas activity5 will be rejected. Therefore at the end of an iteration, activities at index 0, 1, 4, and 6 will be performed, while others get rejected.

Constraints of Activity Selection Problem

$1 ≤ N ≤ 2*10^{5}$

$1 ≤ arr[i] ≤ 10^{9}$

Approach 1: Greedy algorithm

• Intuition:
  This method uses the greedy approach and as the name suggests greedy means that at every step we have to make a choice that looks best at the moment and can provide us with an optimal solution for that problem. Since we have to maximize the number of performed activities, so we will be choosing the activity that will finish first as that will leave us with the maximum time to process the remaining activities. This greedy intuition enables us to make choices and provide us with an optimal solution and also helps us to get started with the solution. Therefore, our first task is to sort the activities based on their finish time. If we try to solve this problem by sorting the activities based on start time then there might be a case where the activity with the least start time takes maximum duration to complete thus preventing us from maximizing the number of activities.
• Algorithm:
  1. Sort all activities based on their finish time.
  2. Choosing the first activity from the sorted list.
  3. Select the next activity from the sorted list only if its start time is greater than or equal to the finish time of the previously selected activity.
  4. Repeat Step 3 for all the remaining activities in the sorted list.
     
• Implementation

C++ Program to solve Activity Selection Problem using Greedy Algorithm:

    #include <bits/stdc++.h>
    using namespace std;

    // An activity has a start, and finish time.
    struct Activity
    {
        int start, finish;
    };

    // Sorting activities by finish time
    bool compare(Activitiy a1, Activitiy a2)
    {
        return (a1.finish < a2.finish);
    }

    void activitySelection(Activity arr[], int n)
    {
        // calling sort function
        sort(arr, arr+n, compare);

        cout << "Selected Actvities are : ";

        // First activity will be always selected
        int i = 0;
        cout << "(" << arr[i].start << ", " << arr[i].finish << ") ";

        // Traversing for remaining activities
        for (int j = 1; j < n; j++)
        {
            // If start time of current activity >= finish time of previous activity
            if (arr[j].start >= arr[i].finish)
            {
                cout << "(" << arr[j].start << ", " << arr[j].finish << ") ";
                i = j;
            }
        }
    }

    int main()
    {
        Activity arr[] = {{3, 4}, {2, 5}, {1, 3}, {5, 9}, {0, 7}, {11, 12}, {8, 10}};

        int n = sizeof(arr)/sizeof(arr[0]);
        // calling selection function
        activitySelection(arr, n);
        
        return 0;
    }

Output:

    Selected Actvities are : (1, 3) (3, 4) (5, 9) (11, 12)

Java Program to solve Activity Selection Problem using Greedy Algorithm:

    import java.io.*;
    import java.util.*;

    // An activity has a start time, and finish time.
    class Activity
    {
        int start, finish;
    
    // Activity Constructor
    public Activity(int start, int finish)
        {
            this.start = start;
            this.finish = finish;
        }
    }

    class Compare
    {
        // Sorting activities by finish time
        static void compare(Activity arr[], int n)
        {
            Arrays.sort(arr, new Comparator<Activity>()
                        {
                        @Override
                        public int compare(Activity s1, Activity s2)
                        {
                            return s1.finish - s2.finish;
                        }
                        });
        }
    }

    class Main 
    {
        static void activitySelection(Activity arr[], int n)
        {
            // calling sorting function
            Compare obj = new Compare();
            obj.compare(arr, n);
            System.out.print("Selected Activities are : ");

            // The first activity will be always selected
            int i = 0;
            System.out.print("(" + arr[i].start + ", "
                            + arr[i].finish + ") ");

            // Traversing remaining activities
            for (int j = 1; j < n; j++)
            {

            // If current activity has start time >= finish time of previously selected activity
            if (arr[j].start >= arr[i].finish)
            {
                System.out.print("(" + arr[j].start + ", "
                                + arr[j].finish + ") ");
                i = j;
            }
        }
    }

    public static void main(String[] args)
    {

        int n = 7;
        Activity arr[] = new Activity[n];
        arr[0] = new Activity(3, 4);
        arr[1] = new Activity(2, 5);
        arr[2] = new Activity(1, 3);
        arr[3] = new Activity(5, 9);
        arr[4] = new Activity(0, 7);
        arr[5] = new Activity(11, 12);
        arr[6] = new Activity(8, 10);

        activitySelection(arr, n);
    }
    }

Output

    Selected Activities are : (1, 3) (3, 4) (5, 9) (11, 12)

Python Program to solve Activity Selection Problem using Greedy Algorithm:

    def activitySelection(arr, n):

        # Sorting activities by finish time
        arr.sort(key = lambda x : x[1])

        # First activity will bealways selected
        i = 0
        print(arr[i], end=' ')

        for j in range(1, n):
        # If the current activity has start time >= finish time of previously selected
        # activity, then select it
            if arr[j][0] >= arr[i][1]:
                print(arr[j], end=' ')
                i = j

    arr = [[3, 4], [2, 5], [1, 3], [5, 9], [0, 7], [11, 12], [8, 10]]
    n = len(arr)

    print("Selected activities are :", end=' ')
    # Calling the selection function 
    activitySelection(arr, n)

Output

    Selected activities are : [1, 3] [3, 4] [5, 9] [11, 12]

• Complexity Analysis:

Complexity Analysis:

Case 1: 

When the provided list of activities is already sorted by finish time, then no need for sorting it again. Therefore, Time Complexity in such a case will be `O(n)`.

Case 1:

When the provided list of activities is not sorted, then we will have to either write a `sort()` function from scratch or we can use the in-built Standard Template Library function. Therefore, Time Complexity, in this case, will be `O(nlogn)`.

Space Complexity:`O(1)`, Since no Auxillary space is required.

Approach 2: Count the maximum number of non-conflicting activities

• Intuition
  This approach involves the use of dynamic programming, as this problem is a variation of Longest Increasing Subsequence (LCS). The intuition is to sort the given array of activities named arr by start time, after which we can create an array named dp, such that dp[i] stores the count of maximum activities that can be performed without conflict.
• Algorithm The recursive way of completing the dp[i] after every i’th activity is:

    dp[i] = arr[i] + {max(dp[j]), where j < i and arr[j].finish <= arr[i].start}
          = arr[i], else

Let us take an example where sorted –

    arr = {{0, 7}, {1, 3}, {2, 5}, {3, 4}, {5, 9}, {8, 10}, {11, 12}} 

For the above example dp[] would be:

    L[0]: {0, 7}
    L[1]: {1, 3}
    L[2]: {2, 5}
    L[3]: {1, 3}, {3, 4}
    L[4]: {1, 3}, {3, 4}, {5, 9}
    L[5]: {1, 3}, {3, 4}, {8, 10}
    L[6]: {1, 3}, {3, 4}, {5, 9}, {11, 12}

• Implementation

C++ Program to Count the maximum number of non-conflicting activities using Dynamic Programming

    #include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;

    struct Activity
    {
        int start, finish;
    };

    int activitySelection(vector<Activity> arr)   
    {
        // sorting the activities in increasing order of their start time
        sort(arr.begin(), arr.end(),
            [](Activity &x, Activity &y) {
                return x.start < y.start;
            });

        // dp[i] stores the maximum count of non-conflicting activities till i'th activity
        vector<int> dp(arr.size());

        for (int i = 0; i < arr.size(); i++)
        {
            for (int j = 0; j < i; j++)
            {
                // when `arr[j].finish` is less than equal to `arr[i].start`
                if (arr[j].finish <= arr[i].start && dp[i] < dp[j]) {
                    dp[i] = dp[j];
                }
            }
            // increment dp[i]
            dp[i]++;
        }
        // return the maximum activity length in the list
        return *max_element(dp.begin(), dp.end());
    }

    int main()
    {
        // arr storing the start and finish of all activities
        vector<Activity> arr = {{3, 4}, {2, 5}, {1, 3}, {5, 9}, {0, 7}, {11, 12}, {8, 10}};

        cout << "The maximum number of non-conflicting activities are " << activitySelection(arr);

        return 0;
    }

Output

    The maximum number of non-conflicting activities are 4

Java Program to Count the maximum number of non-conflicting activities using Dynamic Programming

    import java.util.Arrays;
    import java.util.Collections;
    import java.util.Comparator;
    import java.util.List;

    // A class to store the start and finish time of the activities
    class Activity
    {
        public final int start;     
        public final int finish;

        // Constructor
        private Activity(int start, int finish)
        {
            this.start = start;
            this.finish = finish;
        }

        public static Activity of(int a, int b)
        {
            // calling constructor
            return new Activity(a, b);
        }
    }

    class Main
    {
        public static int activitySelection(List<Activity> arr)
        {
            // sorting the activities in increasing order of their start time
            Collections.sort(arr, Comparator.comparingInt(Activity -> Activity.start));

            // dp[i] stores the maximum count of non-conflicting activities till i'th activity
            int[] dp = new int[arr.size()];

            for (int i = 0; i < arr.size(); i++)
            {
                for (int j = 0; j < i; j++)
                {
                    // when `arr[j].finish` is less than equal to `arr[i].start`
                    if (arr.get(j).finish <= arr.get(i).start && dp[i] < dp[j]) {
                        dp[i] = dp[j];
                    }
                }

                // increment dp[i] 
                dp[i]++;
            }

            // return the maximum activity length in the list
            return Arrays.stream(dp).max().getAsInt();
        }

        public static void main(String[] args)
        {
            // Each pair stores the start and the finish time of an activity
            List<Activity> arr = Arrays.asList(
                    Activity.of(3, 4), Activity.of(2, 5), Activity.of(1, 3),
                    Activity.of(5, 9), Activity.of(0, 7), Activity.of(11, 12),
                    Activity.of(8, 10)
                    );

            System.out.println("The maximum number of non-conflicting activities are " + activitySelection(arr));
        }
    }  

Output

    The maximum number of non-conflicting activities are 4

Python Program to Count the maximum number of non-conflicting activities using Dynamic Programming

    def activitySelection(arr):
 
        # sorting the activities in increasing order of their start time
        arr.sort(key=lambda x: x[0])

        # dp[i] stores the maximum count of non-conflicting activities till i'th activity
        dp = [0] * len(arr)

        for i in range(len(arr)):
            for j in range(i):
                # when `arr[j].finish` is less than equal to `arr[i].start`
                if arr[j][1] <= arr[i][0] and dp[i] < dp[j]:
                    dp[i] = dp[j]

            # increment dp[i]
            dp[i] = dp[i] + 1

        # return the maximum activity length in the list
        return max(dp)

    # arr storing the start and finish of all activities
    arr = [[3, 4], [2, 5], [1, 3], [5, 9], [0, 7], [11, 12], [8, 10]]

    print('The maximum number of non-conflicting activities are', activitySelection(arr))

Output:

    The maximum number of non-conflicting activities are 4

Complexity Analysis

Since we are using nested for-loops to traverse the list of `n` activities `arr`, 
**Time Complexity** :$O(n^{2})$

While we are also using an array named `dp` to store the maximum number of non-conflicting activities,
**Therefore the Space Complexity approach for this approach is:** $O(n)$

Approach 3: Print the maximum number of non-conflicting activities

• Intuition
  The approach for this section is the same as the previous one, but the difference here is that instead of printing the number of non-conflicting activities we have to print all these activities. Therefore, instead of doing dp[i]++, we will be adding arr[i] to dp[i] for every i’th activity.
• Implementation

C++ Program to Print the maximum number of non-conflicting activities using Dynamic Programming

#include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;

    // Struct to store the start and finish time of activities.
    struct Activity
    {
        int start, finish;
    };

    void activitySelection(vector<Activity> arr)       
    {
        // sorting the activities in increasing order of their start time
        sort(arr.begin(), arr.end(),
            [](Activity &x, Activity &y) {
                return x.start < y.start;
            });

        // dp[i] stores the maximum non-conflicting activities till i'th activity
        vector<vector<Activity>> dp(arr.size());

        for (int i = 0; i < arr.size(); i++)
        {
            for (int j = 0; j < i; j++)
            {
                // # when `arr[j].finish` is less than equal to `arr[i].start`
                if (arr[j].finish <= arr[i].start &&
                    dp[i].size() < dp[j].size()) {
                    dp[i] = dp[j];
                }
            }

            // adding arr[i] to dp[i]
            dp[i].push_back(arr[i]);
        }

        // finding the vector having maximum size in dp
        vector<Activity> max;
        for (auto &pair: dp)
        {
            if (max.size() < pair.size()) {
                max = pair;
            }
        }

        // printing activity with start and finish time
        for (Activity &pair: max) {
            cout << "{" << pair.start << ", " << pair.finish << "} ";
        }
    }

    int main()
    {
        // arr storing the start and finish of all activities
        vector<Activity> arr = {{3, 4}, {2, 5}, {1, 3}, {5, 9}, {0, 7}, {11, 12}, {8, 10}};

        cout << "The maximum number of non-conflicting activities are ";
        activitySelection(arr);

        return 0;
    }

Output:

    The maximum number of non-conflicting activities are {1, 3} {3, 4} {5, 9} {11, 12}

Java Program to Print the maximum number of non-conflicting activities using Dynamic Programming

    import java.util.*;

    // A class to store the start and finish time of the activities
    class Activity
    {
        public int start, finish;

        Activity(int start, int finish)
        {
            this.start = start;
            this.finish = finish;
        }

        @Override
        public String toString() {
            return "(" + this.start + ", " + this.finish + ")";
        }
    }

    class Main
    {
        public static void activitySelection(List<Activity> arr)
        {
            // sorting the activities in increasing order of their start time
            Collections.sort(arr, Comparator.comparingInt(x -> x.start));

            // dp[i] stores the maximum non-conflicting activities till i'th activity
            List<List<Activity>> dp = new ArrayList<>();
            for (var Activity: arr) {
                dp.add(new ArrayList<>());
            }

            for (int i = 0; i < arr.size(); i++)
            {
                for (int j = 0; j < i; j++)
                {
                    // when `arr[j].finish` is less than equal to `arr[i].start`
                    if (arr.get(j).finish <= arr.get(i).start && dp.get(i).size() < dp.get(j).size()) {
                        dp.set(i, new ArrayList<>(dp.get(j)));
                    }
                }

                // adding arr[i] to dp[i]
                dp.get(i).add(arr.get(i));
            }

            // finding the vector having a maximum size in dp
            List<Activity> max = dp.stream().max(Comparator.comparingInt(x -> x.size())).get();

            // printing maximum non conflicting activity with start and finish time
            System.out.print(max);
        }

        public static void main(String[] args)
        {
            // Each pair stores the start and the finish time of an activity
                List<Activity> arr = Arrays.asList(new Activity(3, 4), new Activity(2, 5),
                    new Activity(1, 3), new Activity(5, 9),
                    new Activity(0, 7), new Activity(11, 12),
                    new Activity(8, 10));

            System.out.print("The maximum number of non-conflicting activities are ");
            activitySelection(arr);
        }
    }

Output:

    The maximum number of non-conflicting activities are [(1, 3), (3, 4), (5, 9), (11, 12)]

Python Program to Print the maximum number of non-conflicting activities using Dynamic Programming

    def activitySelection(arr):
 
        # sorting the activities in increasing order of their start time
        arr.sort(key=lambda x: x[0])

        # dp[i] stores the maximum non-conflicting activities till i'th activity
        dp = [[] for _ in range(len(arr))]

        for i in range(len(arr)):
            for j in range(i):
                # when `arr[j].finish` is less than equal to `arr[i].start`
                if arr[j][1] < arr[i][0] and len(dp[i]) < len(dp[j]):
                    dp[i] = dp[j].copy()

            # adding arr[i] to dp[i]
            dp[i].append(arr[i])

        # finding the list having maximum size in dp
        ans = []
        for k in dp:
            if len(ans) < len(k):
                ans = k

        # printing the list having maximum non-conflicting activities
        print(ans)

    # arr storing the start and finish of all activities
    arr = [[3, 4], [2, 5], [1, 3], [5, 9], [0, 7], [11, 12], [8, 10]]

    print('Maximum non-conflicting activities are', end=' ')
    activitySelection(arr)

Output

    Maximum non-conflicting activities are [[1, 3], [5, 9], [11, 12]]

Complexity Analysis

Since we are using nested for-loops to traverse the list of `n` activities `arr`, 

Therefore the Time Complexity approach for this approach is: $O(n^{2})$

While we are also using a matrix named dp to store the maximum number of non-conflicting activities,

Therefore the Space Complexity approach for this approach is: $O(n^{2})$

Conclusion

• At every step in the Greedy Approach we have to make a choice that looks best at the moment and can provide us with an optimal solution for that problem.
• Since we had to maximize the number of performed activities, we chose the activity that will finish first as that will leave us with the maximum time to process the remaining activities.
• Time and Space Complexity for the Greedy approach when the given set of activities are not sorted is O(nlogn) and O(1) respectively.
• This second approach involves the use of dynamic programming, as this problem was a variation of Longest Increasing Subsequence (LCS)