Skip to content
CCC Python Course

Exchange arguments, scheduling and greedy proofs

Stage
7
Module
M7.4
Lessons
1

In this module

  • Use exchange arguments to prove a greedy algorithm is optimal.
  • Apply scheduling strategies to interval and deadline problems.
  • Recognize when greedy choices are locally optimal and globally sound.

Before this module

M4.2Sorting with keys, and greedyM2.2Algorithm-first thinking

Lessons

  1. 1Exchange arguments, scheduling and greedy proofs

Practice

Try these on the judge. Each link opens the problem on DMOJ.

  1. 2018 S3
    RoboThieves (opens on DMOJ in a new tab) DMOJ

    Schedule tasks with deadlines to maximise the number of completed jobs.

  2. 2017 S2
    High Tide, Low Tide (opens on DMOJ in a new tab) DMOJ

    Choose non-overlapping intervals to maximise coverage of a timeline.