Algorithm Activity Selection Problem Complete Guide

Algorithm Activity Selection Problem

Understanding the Problem:

Imagine you have a list of events or activities, each with its own start and end times. You want to attend as many of these activities as possible, but you can only be present at one activity at any given time. Which activities should you choose to maximize the number you can attend?

Formal Definition:

Given n activities with start and end times, the task is to select the maximum number of activities such that no two selected activities overlap. Each activity is represented by a pair (s[i], f[i]), where s[i] is the start time of the i-th activity and f[i] is the finish time of the i-th activity. The activities are sorted based on their finish times in ascending order.

Objective: To find the maximum set of mutually compatible (non-overlapping) activities.

Key Concepts:

• Greedy Choice Property: Selecting the activity that finishes the earliest is the optimal choice for the first activity in the subset, because this leaves the most room for the remaining activities.
• Feasible Solution: Any combination of non-overlapping activities.
• Optimal Solution: The combination with the maximum number of non-overlapping activities.

Steps for the Greedy Algorithm:

1. Sort Activities: Arrange all the activities in non-decreasing order based on their finish times (f[i]).
2. Select First Activity: The first activity to be selected in the collection will be the one which finishes the earliest.
3. Iterate and Select: For each subsequent activity, check if the start time of the activity is greater than or equal to the finish time of the last selected activity. If it is, then include this activity in the collection.

Here's a detailed step-by-step description of the Activity Selection Algorithm:

1. Input:
   • A list of n activities, each represented as a tuple or pair (s[i], f[i]) indicating the start and finish times respectively.
2. Process:
   • Sort activities by their finish times. This ensures that the activities considered for selection are ordered from the earliest ending to the latest ending.
   • Initialize an empty set to store the selected activities.
   • Set lastFinishTime to 0, representing the time when the last activity ended.
   • Iterate over the sorted activities:
     • For the currently iterated activity (s[i], f[i]):
       • Check if s[i] >= lastFinishTime. If true, this activity can be included in the collection because it does not overlap with the previously selected activity.
       • Add the current activity to the collection.
       • Update lastFinishTime to f[i].
3. Output:
   • The set of selected activities.

Pseudocode:

function activitySelection(s, f):
    # Step 1: Sort activities in non-decreasing order of their finish times
    let n = length of s
    sort activities based on f
    
    # Step 2: Initialize the set of selected activities and the variable to track the end time of the last selected activity
    selectedActivities = []
    lastFinishTime = 0
    
    # Step 3: Iterate and select activities
    for i from 0 to n - 1:
        if s[i] >= lastFinishTime:
            append activity (s[i], f[i]) to selectedActivities
            update lastFinishTime to f[i]
    
    return selectedActivities

Complexity Analysis:

• Sorting Time: The primary computational step here is sorting, which takes (O(n \log n)).
• Selection Time: The second step of selecting activities is linear, taking (O(n)).

Thus, the overall time complexity of the Activity Selection Problem using a greedy algorithm is dominated by the sorting step, resulting in (O(n \log n)).

Example:

Consider the following set of activities:

| Index | Start Time (s[i]) | Finish Time (f[i]) | |-------|-------------------|--------------------| | 0 | 1 | 3 | | 1 | 3 | 5 | | 2 | 0 | 5 | | 3 | 5 | 8 | | 4 | 8 | 9 | | 5 | 5 | 7 | | 6 | 6 | 10 | | 7 | 8 | 11 | | 8 | 2 | 13 | | 9 | 12 | 14 |

After sorting activities by their finish times, the list becomes:

| Index | Start Time (s[i]) | Finish Time (f[i]) | |-------|-------------------|--------------------| | 0 | 1 | 3 | | 1 | 3 | 5 | | 5 | 5 | 7 | | 3 | 5 | 8 | | 8 | 2 | 13 | | 4 | 8 | 9 | | 7 | 8 | 11 | | 6 | 6 | 10 | | 2 | 0 | 5 | | 9 | 12 | 14 |

Using the greedy algorithm:

1. Select activity 0 (1, 3).
2. Can't select activity 1 (3, 5) since it overlaps with activity 0.
3. Select activity 5 (5, 7).
4. Don’t select activity 3 (5, 8) as it overlaps.
5. Cannot pick up activity 8 (2, 13), as it overlaps with earlier selected activities.
6. Select activity 4 (8, 9).
7. Cannot pick activity 7 (8, 11), as it overlaps with activity 4.
8. Don't select activity 6 (6, 10), as it overlaps with activity 5.
9. Skip activity 2 (0, 5), overlapping with activity 0.
10. Finally, select activity 9 (12, 14).

Selected Activities: [0, 5, 4, 9]

Important Information:

• Real-world Applications: Problems like task scheduling, job allocation, and resource management often use similar approaches.
• Variant Problems: There are various variations of the problem, including weighted versions where each activity has a value and the objective is to maximize the total value.
• Proof of Correctness: To ensure that the greedy approach yields an optimal solution, we need to prove that the solution obtained by the greedy choice is an optimal local choice that leads to a global optimum.

Conclusion: