Greedy Algorithms Interval Scheduling Optimal Substructure

Activity Selection Problem

Select the maximum number of non-overlapping activities from a set of candidates, each with a start and finish time — solved optimally with a greedy approach.

// Problem Statement

Given: A set of n activities where each activity i has a start time s[i] and a finish time f[i]. A single machine (or resource) can only execute one activity at a time.

Goal: Select the maximum number of activities that can be performed by a single machine, such that no two selected activities overlap.

Overlap Rule: Two activities i and j are compatible (non-overlapping) if f[i] ≤ s[j] or f[j] ≤ s[i] — one finishes before or exactly when the other starts.

Greedy Key Insight: Always pick the activity with the earliest finish time among all compatible remaining activities. This locally optimal choice leads to a globally optimal solution.

timeline.svg — Greedy Step-through

Selected

Rejected (overlap)

Currently Evaluating

Pending

Last finish time

Activities sorted by finish time →

Selected set →

Press Next Step to begin the greedy algorithm — activities are pre-sorted by finish time.

Step 0 / 10

Algorithm & Complexity

pseudocode.txt

1// Activity Selection — Greedy
2function activitySelection(activities):
3// Step 1: Sort by finish time
4sort(activities, key=finish_time)
5
6// Step 2: Select first activity
7selected ← [activities[0]]
8last_finish ← activities[0].finish
9
10// Step 3: Greedily pick compatible
11for i from 1 to n-1:
12if activities[i].start ≥ last_finish:
13select(activities[i])
14last_finish ← activities[i].finish
15else:
16reject(activities[i])
17
18return selected

complexity.md

Operation	Time	Space
Sort by finish	O(n log n)	O(1) / O(n)*
Greedy scan	O(n)	O(1)
Total	O(n log n)	O(n)
* If pre-sorted input is given, the full algorithm runs in O(n).

// why greedy works here

The greedy choice property holds: selecting the activity with the earliest finish time never rules out more activities than any other choice. Formally, if an optimal solution skips the earliest-finishing activity A, we can always swap whatever activity B it chose for A without reducing the solution size — since A finishes no later than B, it's at least as compatible with future activities.

Key Concepts

// greedy vs dynamic programming

Activity Selection has both an optimal substructure and the greedy choice property. DP would work but is overkill — it runs in O(n²). The greedy approach is simpler, faster (O(n log n) due to sort), and provably optimal. DP is preferred for Weighted activity selection where each activity has a profit and we maximize total profit.

// exchange argument proof

Correctness is proven via the exchange argument: suppose an optimal solution OPT doesn't include activity a₁ (earliest finish). Let b be OPT's first activity. Replace b with a₁ — since f(a₁) ≤ f(b), this new solution is also valid and has the same size. Repeating shows greedy = optimal.