Gegeven is een reeks van \(n\) uit te voeren taken, die allemaal dezelfde tijd vragen; stel voor de eenvoud dat elke taak 1 tijdseenheid duurt. Voor elke taak is een deadline gegeven, evenals een boete die moet betaald worden als de taak niet tegen de deadline uitgevoerd is. Gevraagd is een planning voor de taken op te stellen, zodanig dat de totale boete geminimaliseerd wordt. Ontwerp hiervoor een gretig algoritme.

Opgave

Implementeer hiervoor de functie plan(taken: list). Deze functie neemt een lijst taken als input en geeft een lijst terug waarin de taken zijn opgeslagen die moeten worden uitgevoerd, zonder dat de deadline wordt overschreden. De taak die op positie i staat in de teruggegeven lijst, wordt op tijdstip i uitgevoerd. De resultaatlijst bevat enkel taken die volgens die planning binnen de deadline uitgevoerd worden. (De resultaatlijst kan ook None bevatten als er op die corresponderende tijdstippen geen taken dienen uitgevoerd te worden.)

Een taak wordt voorgesteld als een tuple tuple(deadline, boete).

Voorbeelden

>>> plan([(4, 5), (10, 6), (3, 4), (5, 10), (4, 8), (5, 13), (2, 4), (7, 17), (5, 12), (3, 9)])
[(4, 8), (3, 9), (5, 10), (5, 12), (5, 13), None, (7, 17), None, None, (10, 6)]

>>> plan([(1, 4), (1, 8), (1, 3), (1, 12), (1, 7)])
[(1, 12)]

>>> plan([(4, 5), (10, 6), (3, 4), (5, 10), (4, 8), (8, 13), (2, 4), (7, 17), (7, 12), (10, 9)])
[(2, 4), (3, 4), (4, 5), (4, 8), (5, 10), (7, 12), (7, 17), (8, 13), (10, 6), (10, 9)]