14.4 Interval Scheduling

Interval scheduling is one of the most important greedy problems. It is often the first example where a greedy algorithm achieves a globally optimal solution while remaining remarkably simple.

The problem appears in operating systems, conference room allocation, CPU scheduling, manufacturing pipelines, booking systems, airline gate assignment, and project planning. Although the applications differ, the mathematical structure remains identical: choose as many non-overlapping intervals as possible.

This chapter develops the complete solution, proves its correctness using exchange arguments, and demonstrates why several seemingly reasonable alternatives fail.

Problem

Given a set of intervals:

$$ (start_i, finish_i) $$

select the maximum number of mutually compatible intervals.

Two intervals are compatible if they do not overlap.

Example:

Activity	Start	Finish
A	1	4
B	3	5
C	0	6
D	5	7
E	8	9
F	5	9

Goal:

Choose the largest possible subset of non-overlapping activities.

Brute Force Approach

The most direct solution examines every subset.

For (n) activities there are:

$$ 2^n $$

possible subsets.

Each subset must be checked for overlap.

Complexity:

$$ O(2^n) $$

This becomes impractical even for moderate values of (n).

We need something better.

Searching for a Greedy Rule

Several intuitive rules suggest themselves.

Earliest Start Time

Choose the activity that starts first.

Example:

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

Selecting A first leaves no room for the others.

Result:

A

Only one activity.

Optimal solution:

B -> C -> D

Three activities.

The rule fails.

Shortest Duration

Choose the shortest interval.

Example:

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

Shortest duration selects C.

Result:

C

Only one activity may remain.

Optimal solution:

A -> B

Two activities.

The rule fails.

Fewest Conflicts

Choose the activity conflicting with the fewest others.

Although appealing, carefully constructed examples show this strategy also fails.

Local conflict counts do not reliably predict future opportunities.

Earliest Finish Time

Now consider:

Select the activity that finishes first.

For the example:

Activity	Start	Finish
A	1	4
B	3	5
C	0	6
D	5	7
E	8	9
F	5	9

Sort by finish time:

Activity	Finish
A	4
B	5
C	6
D	7
E	9
F	9

Choose A.

Remaining compatible activities:

D E F

Choose D.

Remaining:

E

Choose E.

Final schedule:

A -> D -> E

Three activities.

This is optimal.

Greedy Algorithm

Step 1

Sort activities by finish time.

Step 2

Select the first activity.

Step 3

Repeatedly choose the next activity whose start time is not earlier than the finish time of the last selected activity.

Pseudo-code:

Sort by finish time

Select first activity

For each remaining activity:
    If start >= last_finish:
        Select activity

Example Walkthrough

Input:

Activity	Start	Finish
A	1	2
B	3	4
C	0	6
D	5	7
E	8	9

Sorted:

A B C D E

Select A.

Current finish:

2

B starts at 3.

Select B.

Current finish:

4

C starts at 0.

Reject.

D starts at 5.

Select D.

Current finish:

7

E starts at 8.

Select E.

Final schedule:

A -> B -> D -> E

Correctness Proof

The proof uses an exchange argument.

Claim

An optimal schedule exists whose first activity is the activity that finishes earliest.

Proof

Let:

$$ g $$

be the activity with the earliest finish time.

Suppose an optimal schedule begins with activity:

$$ o $$

instead.

Because (g) finishes no later than (o),

$$ finish(g) \le finish(o) $$

Replace (o) with (g).

The replacement cannot invalidate any later activity because (g) leaves at least as much remaining time.

The number of scheduled activities remains unchanged.

Thus an optimal schedule exists beginning with (g).

The greedy choice is safe.

After selecting (g), the remaining problem is:

Schedule as many activities as possible beginning after (finish(g)).

This is exactly the original problem on a smaller set.

By induction, the greedy algorithm is optimal.

Why Earliest Finish Works

The algorithm does not attempt to maximize the duration of an activity.

It does not attempt to minimize overlap.

It simply leaves the largest possible amount of time available for future decisions.

Every earlier finishing activity creates at least as many opportunities as any later finishing activity.

That observation drives the entire proof.

Complexity Analysis

Sorting dominates the running time.

Sorting:

$$ O(n \log n) $$

Single scan:

$$ O(n) $$

Total:

$$ O(n \log n) $$

Space:

$$ O(1) $$

after sorting in place.

Implementation

Go

type Activity struct {
    Start  int
    Finish int
}

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

    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
}

Variations

The basic problem maximizes the number of activities.

Several related problems require different techniques:

Problem	Technique
Maximum number of intervals	Greedy
Minimum intervals removed	Greedy
Weighted interval scheduling	Dynamic programming
Multiple rooms	Priority queues
Interval partitioning	Greedy + heaps
Resource-constrained scheduling	Advanced optimization

The weighted version is especially important.

If each activity has a profit, earliest finish time is no longer sufficient.

Dynamic programming becomes necessary.

Real-World Applications

Meeting Room Booking

Select the maximum number of meetings in a conference room.

CPU Scheduling

Run the largest number of jobs without overlap.

Airport Gates

Assign flights to gates efficiently.

Manufacturing

Schedule machine operations.

Media Broadcasting

Allocate advertising slots.

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

Common Mistakes

Sorting by Start Time

Often produces poor schedules.

Sorting by Duration

Can eliminate valuable future opportunities.

Ignoring Equal End Times

Tie-breaking must preserve finish-time ordering.

Forgetting Sorted Input

The proof assumes activities are processed by finish time.

Without sorting, correctness disappears.

Takeaway

Interval scheduling is the canonical greedy optimization problem. The key insight is that selecting the activity with the earliest finishing time leaves the maximum flexibility for future choices. An exchange argument shows that every optimal solution can be transformed to begin with this greedy choice. After sorting by finish time, a single linear scan constructs an optimal schedule in (O(n \log n)) time, making interval scheduling one of the cleanest and most influential examples of greedy algorithm design.