Activity Selection Problem: A Greedy Approach
The Activity Selection Problem is a classic example of a problem that can be efficiently solved using a greedy algorithm. It involves selecting the maximum number of non-overlapping activities from a given set of activities, each with a defined start and finish time.
Understanding the Problem
Imagine you have a list of activities, each with a start time and a finish time. Your goal is to pick as many activities as possible such that no two selected activities overlap. For instance, if activity A finishes at 10 AM and activity B starts at 9 AM, they overlap. If activity B starts at 10 AM or later, they do not overlap.
To select the maximum number of non-overlapping activities from a given set.
The Greedy Strategy
The greedy approach for the Activity Selection Problem relies on a simple, yet powerful, strategy: always pick the activity that finishes earliest among the remaining compatible activities. This strategy works because by choosing the activity that finishes soonest, we leave the maximum amount of time available for subsequent activities.
Always select the activity that finishes earliest.
The greedy choice is to pick the activity that frees up the resource (e.g., a room, a person) as quickly as possible, allowing more opportunities for other activities.
The formal proof of correctness for this greedy strategy involves showing that there exists an optimal solution that includes the first greedy choice. If an optimal solution does not include the activity that finishes earliest, we can swap it with the first activity in the optimal solution that finishes earliest, and the resulting solution will still be optimal and include the greedy choice.
Algorithm Steps
Loading diagram...
The algorithm begins by sorting all activities in ascending order of their finish times. The first activity in the sorted list is always selected. Then, we iterate through the remaining activities. For each activity, if its start time is greater than or equal to the finish time of the previously selected activity, we select this activity and update the 'last finish time'.
Sort activities by their finish times in ascending order.
Example Walkthrough
Consider activities with (start, finish) times: A(1, 4), B(3, 5), C(0, 6), D(5, 7), E(3, 9), F(5, 9), G(6, 10), H(8, 11), I(8, 12), J(2, 14), K(12, 16).
- Sort by finish time: A(1, 4), B(3, 5), C(0, 6), D(5, 7), E(3, 9), F(5, 9), G(6, 10), H(8, 11), I(8, 12), J(2, 14), K(12, 16).
- Select A (finishes at 4).
- Next compatible activity: D (starts at 5 >= 4). Select D (finishes at 7).
- Next compatible activity: G (starts at 6 >= 7 is false). Skip G.
- Next compatible activity: H (starts at 8 >= 7). Select H (finishes at 11).
- Next compatible activity: K (starts at 12 >= 11). Select K (finishes at 16).
Selected activities: A, D, H, K. Total: 4.
Visualizing the Activity Selection Problem: Imagine a timeline. Each activity is a segment on this timeline. The goal is to pick the maximum number of segments such that no two chosen segments overlap. The greedy strategy picks the segment that ends earliest, then looks for the next segment that starts after the first one ends and also ends earliest among the remaining compatible segments.
Text-based content
Library pages focus on text content
The greedy choice property is crucial here: making the locally optimal choice (picking the earliest finishing activity) leads to a globally optimal solution.
Complexity Analysis
The time complexity of the Activity Selection Problem using the greedy approach is dominated by the sorting step. If there are 'n' activities, sorting takes O(n log n) time. The subsequent iteration to select activities takes O(n) time. Therefore, the overall time complexity is O(n log n).
O(n log n), due to the sorting step.
Comparison with Dynamic Programming
| Feature | Greedy Approach | Dynamic Programming |
|---|---|---|
| Strategy | Make locally optimal choice (earliest finish time) | Solve subproblems and combine results |
| Complexity | O(n log n) | O(n^2) or O(n log n) depending on implementation |
| Simplicity | Simpler to understand and implement | More complex, requires defining recurrence relation |
| Applicability | Optimal for standard Activity Selection | Can solve variations or more complex scheduling problems |
While dynamic programming can also solve the Activity Selection Problem, the greedy approach is generally preferred due to its simplicity and efficiency, provided the problem structure allows for a greedy solution.
Learning Resources
A comprehensive explanation of the Activity Selection Problem, including its greedy solution, algorithm, and complexity analysis.
Learn the greedy approach to the Activity Selection Problem with clear examples and a step-by-step explanation.
Provides a detailed overview of the problem, the greedy strategy, and a C++ implementation.
A visual explanation of the Activity Selection Problem and its greedy solution, often helpful for understanding the concept.
An excerpt from a renowned algorithms textbook covering greedy algorithms, including the Activity Selection Problem.
The Wikipedia page offers a concise definition, problem statement, and discussion of the greedy algorithm's correctness.
Official syllabus for GATE Computer Science, which lists 'Algorithms' as a core subject where this topic is relevant.
This blog post helps differentiate between greedy and dynamic programming approaches, providing context for why greedy is suitable here.
A blog post on Codeforces discussing greedy algorithms in competitive programming, often featuring problems like Activity Selection.
Lecture notes from a university algorithms course that cover greedy algorithms and their applications, including Activity Selection.