Gegeven een collectie van \(n\) taken die op een enkele resource moeten uitgevoerd worden. De resource is beschikbaar vanaf tijdstip \(0\). Elke taak \(i\) heeft een deadline \(d_i\) en heeft de resource nodig voor een onafgebroken tijdsinterval van lengte \(t_i\). Een taak kan op elk willekeurig moment voor haar deadline ingepland worden. Verschillende taken moeten op niet-overlappende tijdsintervallen ingepland worden.

We moeten elke taak inplannen, maar het is toegestaan om bepaalde taken “met vertraging” uit te voeren. Het algoritme moet voor elke taak \(i\) een starttijd \(s(i)\) bepalen; de eindtijd van taak \(i\) is dan \(f(i) = s(i) + t_i\). We noemen een taak vertraagd als haar eindtijd na haar deadline valt: \(f(i) > d_i\); de vertraging is dan \(l_i = f(i)-d_i\); voor een niet-vertraagde taak zetten we \(l_i = 0\).

Het is de bedoeling de taken niet-overlappend zo in te plannen dat de maximale vertraging zo klein mogelijk wordt, m.a.w. we willen \(L = max_i l_i\) minimaliseren. Ontwerp en implementeer een gretig algoritme voor dit probleem.

Opgave

Schrijf een Python-functie schedule(taken: list) die een lijst van taken als input geeft. Een taak wordt voorgesteld als een tuple tuple(taak label, lengte, deadline). Als output wordt een lijst van tuples verwacht tuple(taak label, start uitvoeren, eind uitvoeren) gesorteerd op volgorde van uitvoeren.

Voorbeelden

>>> schedule([('a', 1, 7), ('b', 2, 5), ('c', 3, 5), ('d', 4, 6)])
[('b', 0, 2), ('c', 2, 5), ('d', 5, 9), ('a', 9, 10)]
>>> schedule([])
[]