concept · INFO-CS-ADS-184Activity Selection Problem
Learn how a greedy algorithm selects the maximum number of non-overlapping activities by repeatedly choosing the activity that finishes earliest.
Explanation
Overview
The Activity Selection Problem is a scheduling problem in which a person or resource is available for a collection of activities, each having a start time and finish time. The objective is to select the largest possible number of mutually compatible activities, meaning that no selected activities overlap.
Key concepts
Greedy choice; Earliest finishing time; Activity compatibility; Interval scheduling; Optimal substructure; Greedy-choice property
Variables
start[i]: The starting time of activity i.; finish[i]: The finishing time of activity i.; n: The total number of available activities.; selected: The collection of activities chosen by the algorithm.
Complexity
sorting: O(n log n) time.; selection: O(n) time after sorting.; overall: O(n log n) time and O(n) space if the selected activities are stored separately.; alreadySorted: O(n) time when activities are already sorted by finishing time.
Example
activities: name: A; start: 1; finish: 4; name: B; start: 3; finish: 5; selectedActivities: A; D; maximumActivities: 3; explanation: The activities are considered in increasing order of finishing time. Activity A finishes first, followed by compatible activity D and then E. This produces three non-overlapping activities.
Pseudocode
function activitySelection(activities):
sort activities by finish time
selected = []
lastFinish = -infinity
for activity in activities:
if activity.start >= lastFinish:
selected.append(activity)
lastFinish = activity.finish
return selected
Applications
Meeting-room scheduling.; Classroom and lecture scheduling.; Single-resource task planning.; Event scheduling.; Selecting non-overlapping reservations.
Variables
Start[i]
The starting time of activity i.
Finish[i]
The finishing time of activity i.
N
The total number of available activities.
Selected
The collection of activities chosen by the algorithm.
Example or application
Activities
| Name | Start | Finish |
|---|
A | 1 | 4 |
B | 3 | 5 |
C | 0 | 6 |
D | 5 | 7 |
E | 8 | 9 |
F | 5 | 9 |
Explanation
The activities are considered in increasing order of finishing time. Activity A finishes first, followed by compatible activity D and then E. This produces three non-overlapping activities.
Definition
The Activity Selection Problem is a scheduling problem in which a person or resource is available for a collection of activities, each having a start time and finish time. The objective is to select the largest possible number of mutually compatible activities, meaning that no selected activities overlap.
Mathematical Representation
Select activity i after activity j when start[i] >= finish[j]. The greedy strategy chooses the compatible activity with the earliest finishing time.
Greedy Strategy
Sort all activities by their finishing times in ascending order.
Select the activity that finishes earliest.
For each remaining activity, check whether its starting time is at or after the finishing time of the last selected activity.
Select the activity if it is compatible.
Continue until all activities have been examined.
Pseudocode
function activitySelection(activities):
sort activities by finish time
selected = []
lastFinish = -infinity
for activity in activities:
if activity.start >= lastFinish:
selected.append(activity)
lastFinish = activity.finish
return selected
Complexity
Selection
O(n) time after sorting.
Overall
O(n log n) time and O(n) space if the selected activities are stored separately.
Already Sorted
O(n) time when activities are already sorted by finishing time.
Key Concepts
Greedy choice
Earliest finishing time
Activity compatibility
Interval scheduling
Optimal substructure
Greedy-choice property
Advantages
Produces an optimal solution for the standard unweighted activity selection problem.
Has a simple and efficient implementation.
Can be implemented in linear time after sorting.
Works well for selecting maximum numbers of non-overlapping intervals.
Limitations
The earliest-finish-time strategy does not automatically solve weighted activity selection.
Additional constraints, such as multiple resources or activity priorities, require different approaches.
The standard problem assumes each activity uses the same single resource.
Applications
Meeting-room scheduling.
Classroom and lecture scheduling.
Single-resource task planning.
Event scheduling.
Selecting non-overlapping reservations.
Practice Question
Why does the Activity Selection Problem choose the activity with the earliest finishing time?
Practice Answer
It leaves the maximum possible remaining time for selecting compatible activities and can be proven to produce an optimal solution.
Learning Objectives
Explain the central idea and purpose of activity selection problem.
Identify the assumptions, inputs, and conditions relevant to activity selection problem.
Evaluate an application of activity selection problem for correctness and practical resource requirements.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Greedy Algorithms and Optimization
Suggest a correction or source · More in Algorithms & Data Structures