Gegeven is 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.

Implementeer de interface Scheduler¹ in een klasse MinimizeLatenessScheduler. Implementeer hiervoor de methode Map<Task, Integer> schedule(Collection<Task> tasks). Deze methode neemt een collectie taken als input en geeft een map terug die voor elke taak de geplande starttijd geeft.

Een object van de klasse Task² houdt in twee velden bij wat de deadline van het object is en hoeveel tijd ervoor nodig is.

Opmerking: pas de collectie met taken uit de input niet aan. Indien je dit wel doet, zullen de testen falen.

Gebruik eventueel de testklasse SimpleTest³ om je oplossing lokaal te testen. Je kan hierin eenvoudig extra testgevallen toevoegen.