14.5 Activity Selection

The activity selection problem is historically one of the first optimization problems used to demonstrate the power of greedy algorithms. Although it is mathematically equivalent to interval scheduling, it deserves separate study because it introduces a broader design pattern:

When resources are limited and tasks compete for those resources, selecting the task that leaves the most flexibility for future decisions often leads to an optimal solution.

This principle appears repeatedly throughout greedy algorithm design, from CPU scheduling and network allocation to manufacturing systems and project management.

Problem

A resource can serve only one activity at a time.

Given a collection of activities:

$$ (s_i, f_i) $$

where:

• (s_i) is the start time
• (f_i) is the finish time

Select the largest possible set of mutually compatible activities.

Two activities are compatible if:

$$ s_j \ge f_i $$

or

$$ s_i \ge f_j $$

for every selected pair.

Example

Consider:

Activity	Start	Finish
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

Goal:

Select the maximum number of compatible activities.

Visual Representation

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]

Many activities overlap.

Only a subset can be chosen.

Greedy Observation

Suppose we choose an activity that ends late.

[1----------------12]

Many future opportunities disappear.

Suppose instead we choose an activity that ends early.

[1---3]

More future activities remain available.

This suggests the greedy rule:

Always select the activity that finishes earliest.

This is identical to the interval scheduling strategy.

Algorithm

Step 1

Sort activities by finish time.

Step 2

Select the earliest-finishing activity.

Step 3

Discard all overlapping activities.

Step 4

Repeat on the remaining activities.

Pseudo-code:

Sort by finish time

Choose first activity

For each activity:
    If activity.start >= current_finish:
        Choose activity

Walkthrough

Sort the example by finish time.

Activity	Finish
A	4
B	5
C	6
D	7
E	9
F	9
G	10
H	11
I	12
J	14
K	16

Select A

A

Current finish:

4

Scan Remaining Activities

B overlaps.

C overlaps.

D starts at 5.

Select D.

A -> D

Current finish:

7

Continue

E overlaps.

F overlaps.

G overlaps.

H starts at 8.

Select H.

A -> D -> H

Current finish:

11

Continue

I overlaps.

J overlaps.

K starts at 12.

Select K.

Final solution:

A -> D -> H -> K

Four activities.

No larger feasible solution exists.

Why Earliest Finish Is Optimal

The proof follows the exchange argument introduced earlier.

Let:

$$ g $$

be the earliest-finishing activity.

Assume an optimal solution begins with another activity:

$$ o $$

Because:

$$ f(g) \le f(o) $$

replace (o) with (g).

Every later activity that was compatible with (o) remains compatible with (g).

Therefore:

• Feasibility is preserved.
• Number of activities is unchanged.

An optimal solution exists that begins with the greedy choice.

After selecting (g), the remaining problem is identical to the original problem but smaller.

The argument repeats recursively.

Recursive View

The algorithm repeatedly solves:

Select the earliest-finishing activity.

Then:

Solve the remaining activity selection problem beginning after that finish time.

The recursive structure explains why the greedy algorithm works.

Each local choice creates a smaller instance of the same optimization problem.

Iterative Implementation

The recursive formulation is useful for proofs.

Practical implementations use iteration.

Go

type Activity struct {
	Start  int
	Finish int
}

func SelectActivities(a []Activity) []Activity {
	sort.Slice(a, func(i, j int) bool {
		return a[i].Finish < a[j].Finish
	})

	if len(a) == 0 {
		return nil
	}

	result := []Activity{a[0]}
	lastFinish := a[0].Finish

	for i := 1; i < len(a); i++ {
		if a[i].Start >= lastFinish {
			result = append(result, a[i])
			lastFinish = a[i].Finish
		}
	}

	return result
}

Complexity Analysis

Sorting:

$$ O(n \log n) $$

Selection scan:

$$ O(n) $$

Total:

$$ O(n \log n) $$

Space:

$$ O(1) $$

excluding the output list.

Why Other Greedy Rules Fail

Earliest Start Time

Example:

Activity	Start	Finish
A	1	10
B	2	3
C	3	4
D	4	5

Choosing A first yields:

A

One activity.

Optimal:

B -> C -> D

Three activities.

Shortest Duration

Example:

Activity	Start	Finish
A	1	4
B	4	7
C	3	5

Shortest duration chooses C.

Optimal solution chooses:

A -> B

The heuristic fails.

Least Overlap

Local conflict counts do not necessarily maximize future opportunities.

Counterexamples are easy to construct.

Earliest Finish Principle

A useful way to remember the proof is:

Every activity occupies time.

Earlier finishing activities occupy less future time.

Less occupied future time means more scheduling opportunities.

The greedy algorithm always preserves the largest possible future search space.

Applications

Conference Scheduling

Assign presentations to a room.

Manufacturing Systems

Schedule machine operations.

Reservation Systems

Allocate resources to customers.

CPU Job Scheduling

Execute tasks without overlap.

Satellite Communication

Assign transmission windows.

Airport Runways

Schedule takeoffs and landings.

Each application reduces to selecting a maximum-size compatible subset.

Relationship to Interval Scheduling

Many texts treat interval scheduling and activity selection as identical problems.

In practice:

• Interval scheduling emphasizes intervals.
• Activity selection emphasizes tasks competing for a resource.

The underlying algorithm remains the same.

Studying both viewpoints helps build intuition that transfers to more complex scheduling problems.

Takeaway

The activity selection problem demonstrates one of the most important principles in greedy optimization: choose the option that leaves the most room for future decisions. Sorting activities by finishing time and repeatedly selecting the earliest-finishing compatible activity produces an optimal solution in (O(n \log n)) time. The correctness proof follows directly from an exchange argument showing that every optimal schedule can be transformed to begin with the greedy choice. This pattern becomes the foundation for many scheduling and resource-allocation algorithms encountered later in algorithm design.