LESSON 13 · PATTERN GUIDE

Greedy Scheduling / Sorting

Sort by a useful criterion and make locally optimal choices when an exchange argument supports them.

FIRST, LEARN THE PATTERNA greedy strategy commits to a locally best option and relies on a proof that this choice can be part of an optimal solution.

The task involves scheduling, jumps, assigning resources, or selecting a maximum compatible set.

How to approach it

Identify the choice rule, test it on edge cases, then justify why swapping an optimal solution to use your choice cannot make it worse.

Watch out for

A plausible greedy rule is not proof. Some optimization problems require dynamic programming instead.

A CLOSER EXPLANATION

A greedy algorithm makes one locally best choice at a time. Sorting usually makes that choice easy to identify, but correctness needs a reason: for example, choosing the activity that finishes earliest leaves at least as much time for everything else. If no such argument holds, consider DP or search.

NOW YOU TRY

Practice question

What is the maximum number of non-overlapping activities: [1,3], [2,4], [3,5], [5,7]?

EXAMPLEactivities = [[1,3], [2,4], [3,5], [5,7]]Give your answer before revealing the explanation.

Show a hint

Sort by end time and repeatedly choose the earliest-finishing compatible activity.

Show an answer

3 activities: [1,3], [3,5], [5,7] when touching endpoints are allowed.

CONNECT IT TO REAL LIFE

Greedy Scheduling / Sorting at work

One technician can handle one repair at a time. Jobs occupy [1,3], [2,4], [3,5], and [5,7]. What is the largest number of jobs they can finish if one may start exactly when another ends?

Show one possible approach

3 jobs: [1,3], [3,5], and [5,7]. Sorting by finish time lets you repeatedly take the compatible job that frees the technician soonest.

Practice next

Use these problem IDs to find additional practice for this pattern:

4555406621763134