Activity Selection Problem

Problem Statement

Select the maximum number of activities that don’t overlap.

Example: Activities = [(1,3),(2,4),(3,5)] → Output: 2

Approach 1: Brute Force

Try all subsets of activities and count non-overlapping ones.

Time Complexity: O(2^n)

Space Complexity: O(n)

for each subset of activities:
    if no two activities overlap:
        count++
return maximum count

💡 Think: Try every subset and keep the largest set with no overlaps—exhaustive but exponential.

Approach 2: Better

Sort by start time and recursively select compatible activities.

Time Complexity: O(n^2)

Space Complexity: O(n)

sort activities by start time
function selectActivities(current, activities):
    for next in activities after current:
        if next.start >= current.end:
            count++
            selectActivities(next, activities)
return maximum count

💡 Think: Sort by start times and explore next compatible choices recursively for larger chains.

Approach 3: Optimal Greedy

Sort by finish time and iteratively select next compatible activity.

Time Complexity: O(n log n)

Space Complexity: O(1)

sort activities by finish time
lastSelected = first activity
count = 1
for each activity in sorted list:
    if activity.start >= lastSelected.end:
        select activity
        lastSelected = activity
        count++
return count

💡 Think: Sort by earliest finish and always pick the next activity starting after the last finish.

Solve on LeetCode