Activity Selection Problem

Overview

The Activity Selection Problem is a classic example of a greedy algorithm where you have to select the maximum number of activities that don't overlap in time from a given set of activities with start and finish times.

Problem Statement

You are given N activities with their start and finish times. You need to select the maximum number of activities that can be performed by a single person, assuming that only one activity can be done at a time.

Approach (Greedy Algorithm)

• Sort all activities based on their finishing times in ascending order.
• Select the first activity and add it to the result.
• For every next activity, select it if the start time is greater than or equal to the finish time of the previously selected activity.
• Repeat until all activities are checked.

Python Code Implementation

def activity_selection(start, finish):
    n = len(start)
    activities = sorted(zip(start, finish), key=lambda x: x[1])

    selected = [activities[0]]
    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

start = [1, 3, 0, 5, 8, 5]
finish = [2, 4, 6, 7, 9, 9]

result = activity_selection(start, finish)
print("Selected activities (start, finish):")
for s, f in result:
    print(f"({s}, {f})")

Example

Input: start[] = {1, 3, 0, 5, 8, 5}, finish[] = {2, 4, 6, 7, 9, 9}

Output: Selected activities (start, finish): (1, 2), (3, 4), (5, 7), (8, 9)

Time Complexity

The time complexity is O(n log n) due to sorting; selection takes O(n).