CMD + K

Kapittel 7 · Grådige algoritmer
grådige algoritmer

Aktivitetsvalg: ta den som slutter først

1:04Fortellerstemme
0:00 / 0:00

Sju aktiviteter vil bruke det samme rommet på overlappende tider — hvor mange rekker du? Det grådige trikset er å sortere etter slutttid (ikke start, ikke lengde) og plukke den første som ikke kolliderer med det forrige valget. Søylene tegnes usortert på en tidslinje, glir på plass etter slutt, og en grense-strek vandrer høyrover mens fire aktiviteter lyser amber og de overlappende dimmes. Lander på sortering pluss ett gjennomløp, og at grådig faktisk er optimalt for dette problemet.