1 / 5 Greedy & Exchange Arguments

The Short Class Trap

Four classes, drawn on a shared timeline:

Class B is the shortest bar but it overlaps both A and C A B C D 0 5 10 15 20 25
class start finish duration
A 0 10 10
B 9 12 3
C 11 20 9
D 20 25 5

Run the shortest-duration rule: repeatedly take the shortest remaining class, discard everything that conflicts with it, recurse. How many classes does it schedule, and what is the optimum?

A

It schedules 1. The optimum is 3.

B

It schedules 2. The optimum is 3.

C

It schedules 3, which is the optimum.

D

It schedules 2. The optimum is 4.