Activity Selection Problem: Classic Greedy Algorithm Explained with Examples

The Activity Selection Problem is a renowned example in algorithms illustrating how the greedy approach can efficiently optimize resource usage over time. It’s a classic problem that seeks to select the maximum number of mutually compatible activities (non-overlapping in time) from a given set, based on their start and finish times. This article offers an in-depth guide to understanding, implementing, and visualizing the greedy algorithm solution for this fundamental problem.

What is the Activity Selection Problem?

You are given a list of activities, each defined by a start time and a finish time. The goal is to select the maximum number of activities that don’t overlap, meaning no two selected activities run concurrently. The problem arises in contexts like scheduling lectures, meetings, jobs, or booking resources efficiently.

Problem Definition

• Input: Arrays of start times start[] and finish times finish[] for n activities.
• Output: Largest subset of mutually compatible activities.

Example of Input Activities

Why Use a Greedy Algorithm?

The Activity Selection Problem perfectly exemplifies a greedy strategy because by always picking the activity that finishes earliest, it maximizes the possibility of fitting in more activities later. The greedy property here is choosing a locally optimal solution at each stage – the activity that frees up time the soonest.

Key Greedy Choice Property

• Pick the activity with the earliest finish time that is compatible with previously selected activities.
• Repeat this process until no more compatible activities remain.

Step-by-Step Example

Let’s apply the greedy algorithm to the example provided.

1. Sort activities by their finish time:
   • A1 (Finish: 4), A2 (5), A4 (7), A3 (6), A6 (9), A5 (9)
2. Select the first activity: A1 (1,4).
3. Check next: A2 starts at 3, which overlaps with A1’s finish, skip.
4. Check A3 starts at 0 (before A1 finishes), skip.
5. Check A4 starts at 5 (after A1 finishes), select A4.
6. Check A5 starts at 8 (after A4 finishes), select A5.
7. Check A6 starts at 5, overlaps with A4, skip.

Final Set of Selected Activities:

A1, A4, A5 — The maximum compatible activities set.

Classic Greedy Algorithm Implementation (Python)

def activity_selection(start, finish):
    n = len(start)
    # Combine and sort activities by finish time
    activities = sorted(zip(start, finish), key=lambda x: x[1])

    selected = [activities[0]]  # select first activity
    last_finish = activities[0][1]

    for i in range(1, n):
        if activities[i][0] >= last_finish:
            selected.append(activities[i])
            last_finish = activities[i][1]

    return selected

# Example
start_times = [1, 3, 0, 5, 8, 5]
finish_times = [4, 5, 6, 7, 9, 9]

result = activity_selection(start_times, finish_times)
print("Selected activities (start, finish):", result)

Output:

Selected activities (start, finish): [(1, 4), (5, 7), (8, 9)]

Visualizing Activity Selection on a Timeline

Below is a timeline visualization showing the start and finish of each activity and the selected subset highlighted, for better intuitive understanding.

Why Greedy Works Here? Proof Sketch

The greedy choice – selecting the earliest finishing activity – is safe because:

• Any optimal solution must include some activity that finishes earliest.
• Choosing the earliest finishing activity leaves the maximum remaining time for other activities.
• This local optimum leads to a globally optimal solution, as no other choice can yield more selected activities.

Interactive Thought Experiment

Try varying the start and finish times of activities below and see how the selected set changes in real time (conceptual example):

// Pseudo-interactive code idea (for real use, JavaScript or online tools needed)

Activities:
(2, 4), (3, 5), (1, 6), (5, 7), (8, 9)

Try changing finish times or start times and rerun the greedy selection.
Watch how maximum number of non-overlapping activities updates.

Conclusion

The Activity Selection Problem is a foundational example that clearly demonstrates the power and simplicity of greedy algorithms. By always choosing the earliest finishing compatible activity, we obtain an optimal scheduling solution efficiently. This principle extends to many real-life scheduling and resource allocation problems, making understanding this classic algorithm critical for computer science learners and professionals alike.

Master this algorithm and its visualizations to boost algorithmic thinking and prepare for more complex optimization problems.