Q3Design and Analysis of Algorithms
Question
Explain the activity selection problem using the Greedy approach.
Answer
The Activity Selection Problem greedily selects the maximum number of non-overlapping activities by always picking the activity that finishes earliest.
The Activity Selection Problem: Given n activities each with start time sᵢ and finish time fᵢ, select the maximum number of mutually compatible (non-overlapping) activities. Two activities i and j are compatible if their intervals don't overlap (fᵢ ≤ sⱼ or fⱼ ≤ sᵢ).
- Sort all activities by their finish time in non-decreasing order.
- Select the first activity (earliest finish time).
- For each subsequent activity: if its start time ≥ finish time of the last selected activity, select it.
- Repeat until all activities are considered.
Activities sorted by finish time: A1(1,4), A2(3,5), A3(0,6), A4(5,7), A5(8,9), A6(5,9). Select A1(f=4), next: A4(s=5≥4, select, f=7), next: A5(s=8≥7, select). Optimal selection: {A1, A4, A5} with 3 activities.
Why greedy works: The activity finishing earliest leaves maximum room for remaining activities. Greedy Choice Property is provable by exchange argument. Time Complexity: O(n log n) for sorting + O(n) for selection = O(n log n).