Activity Selection Problem

Given a set of activities with start and finish times, select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a time.

Activity Selection

Ready

Intuition

Imagine you have a single meeting room and a list of requested meetings with start and end times. You want to accommodate as many meetings as possible. Intuition might say "pick the shortest meetings" or "pick the earliest starting meetings", but the correct greedy strategy is to always pick the meeting that finishes earliest. This leaves the maximum amount of time remaining for other meetings.

Concept

The Greedy Choice: Sort all activities by their finish time. Always pick the first available activity that doesn't overlap with the previously selected one.

This works because choosing the activity that finishes first leaves the resources free for the longest remaining time, maximizing the chance to fit in more activities.

How it Works

Sort: Sort all activities based on their finish times in non-decreasing order.
Select First: Always select the first activity (it finishes earliest).
Iterate: For each remaining activity:
- If its start time is greater than or equal to the finish time of the last selected activity, select it.
- Otherwise, skip it (it overlaps).

Step-by-Step Breakdown

Consider activities: (1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14), (12,16)

Sort by End Time: (1,4), (3,5), (0,6), (5,7), (5,9), (3,9), (6,10), (8,11), (8,12), (2,14), (12,16)
Select (1,4): Ends at 4. (Last End = 4)
Check (3,5): Start 3 < 4. Reject.
Check (0,6): Start 0 < 4. Reject.
Check (5,7): Start 5 >= 4. Select. (Last End = 7)
... Continue ...

Pseudocode

sort(activities, by=finish_time)

last_finish = -1

count = 0

for activity in activities:

if activity.start ≥ last_finish:

select(activity)

last_finish = activity.end

count++

else: reject()

Time: O(N log N) (Sorting)Space: O(1)

When to Use

Scheduling meetings in a single room.
Task scheduling on a single processor.
Any interval problem where you want to maximize the count of non-overlapping intervals.

When NOT to Use

If activities have different values or weights (use Weighted Interval Scheduling with DP).
If multiple resources (rooms/machines) are available.

How to Identify

Keywords: "Maximum number of activities", "Non-overlapping intervals", "Single resource".

Sample Problems

N meetings in one room

Standard Activity Selection.

Non-overlapping Intervals

Find min removal to make rest non-overlapping (equivalent to max selection).

Introduction

Huffman Coding

Frequently Asked Questions

What is the Greedy choice for Activity Selection?

Always choose the activity that finishes first among the remaining available tasks. This leaves the maximum possible room for later activities.

Why sort by finish time?

Sorting by finish time allows the algorithm to be as "greedy" as possible by freeing up the resources at the earliest possible time.

Complexity of Activity Selection?

O(n log n) due to the mandatory sorting step. Once sorted, the selection pass takes O(n) time.