✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-184

Activity 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

NameStartFinish

A

1

4

B

3

5

C

0

6

D

5

7

E

8

9

F

5

9

Selected Activities

  • A

  • D

  • E

Maximum Activities

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.

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

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.

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.

Related Topics

  • Interval Scheduling

  • Job Sequencing with Deadlines

  • Greedy Algorithms

  • Scheduling Algorithms

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