Activity Selection Problem
The Activity Selection Problem is one of the most popular applications of the Greedy Method. The objective is to select the maximum number of activities that can be performed by a single person or resource without any overlap in their execution time.
Each activity has a starting time and a finishing time. A person can perform only one activity at a time. The Greedy strategy selects the activity that finishes earliest so that maximum time remains available for the remaining activities.
Problem Statement
Given a set of activities with their starting and finishing times, select the largest possible set of non-overlapping activities that can be completed by a single person.
Real-Life Example
Suppose a seminar hall is booked for different presentations throughout the day. Since only one presentation can be conducted at a time, the organizer wants to schedule the maximum number of presentations without any overlap.
The Greedy approach always selects the presentation that finishes first, leaving more time for the remaining presentations.
Input Activities
| Activity | Start Time | Finish Time |
|---|---|---|
| A1 | 1 | 2 |
| A2 | 3 | 4 |
| A3 | 0 | 6 |
| A4 | 5 | 7 |
| A5 | 8 | 9 |
| A6 | 5 | 9 |
Working Principle
The Greedy algorithm follows these steps:
- Arrange the activities in ascending order of finishing time.
- Select the activity that finishes first.
- Ignore all activities that overlap with the selected activity.
- Select the next activity whose starting time is greater than or equal to the finish time of the previously selected activity.
- Repeat the process until all activities are considered.
Illustration
Step-by-Step Example
| Step | Selected Activity | Reason |
|---|---|---|
| 1 | A1 | Finishes first. |
| 2 | A2 | Starts after A1 finishes. |
| 3 | A4 | Starts after A2 finishes. |
| 4 | A5 | Starts after A4 finishes. |
Activity Selection Algorithm
ActivitySelection(Activities)
Step 1 : Sort all activities according to their finishing times.
Step 2 : Select the first activity.
Step 3 : Compare the finish time of the selected activity with the start time of the next activity.
Step 4 : If the next activity starts after or at the finish time of the selected activity, select it.
Step 5 : Repeat the process until all activities are examined.
Step 6 : Display the selected activities.
Complexity Analysis
| Case | Complexity | Explanation |
|---|---|---|
| Sorting Activities | O(n log n) | Activities are sorted according to their finishing times. |
| Selecting Activities | O(n) | Each activity is visited only once after sorting. |
| Total Time Complexity | O(n log n) | Sorting dominates the overall running time. |
| Space Complexity | O(1) | Only a few variables are required apart from the input array. |
Advantages
- Simple and easy to understand.
- Produces an optimal solution for the Activity Selection Problem.
- Efficient due to Greedy strategy.
- Suitable for scheduling applications.
- Requires very little additional memory.
Limitations
- Applicable only when the Greedy Choice Property holds.
- Cannot solve every optimization problem.
- Activities must be considered according to their finishing times.
- Does not work correctly for problems lacking Optimal Substructure.
Applications
| Application | Description |
|---|---|
| Class Scheduling | Scheduling maximum lectures without overlap. |
| Conference Management | Allocating seminar halls efficiently. |
| CPU Scheduling | Selecting non-overlapping processes. |
| Resource Allocation | Efficient utilization of limited resources. |
| Project Planning | Selecting compatible project activities. |
Activity Selection vs Fractional Knapsack
| Activity Selection | Fractional Knapsack |
|---|---|
| Selects maximum compatible activities. | Maximizes total profit. |
| Selection based on finishing time. | Selection based on profit-to-weight ratio. |
| Activities cannot overlap. | Items can be taken fractionally. |
| Scheduling Problem. | Optimization Problem. |