Gegeven is een verzameling jobs waarbij elke job een vooraf bepaalde start- en eindtijd heeft. Twee jobs zijn compatibel als hun uitvoeringsinterval niet overlapt. Het doel is om een zo groot mogelijke deelverzameling van wederzijds compatibele jobs te selecteren.

Er wordt gevraagd om een optimaal selectie-algoritme met polynomiale uitvoeringstijd te implementeren.

Hint: ga bijvoorbeeld op zoek naar een gretige strategie die start met een lege selectie en stap voor stap jobs toevoegt volgens een bepaald selectiecriterium. Denk er grondig over na welk criterium tot een optimale oplossing leidt. Eventueel kan je enkele strategieën uitproberen. Probeer de verschillen te verklaren en in te zien waarom een bepaalde strategie al dan niet altijd het optimum vindt.

Voorbeeld

In het onderstaande voorbeeld bevat de optimale selectie 3 jobs (b, e, h). Deze zijn allemaal compatibel met elkaar. Alle resterende jobs zijn incompatibel met minstens één geselecteerde job en er bestaat geen grotere geldige selectie.

Implementeer de interface Scheduler¹ in een klasse genaamd IntervalScheduler. Hiervoor schrijf je een methode public Set<Job> select(List<Job> jobs), die een lijst jobs als argument heeft en de grootst mogelijke verzameling wederzijds compatibele jobs teruggeeft. Maak hierbij gebruik van de gegeven klasse Job², waarbij elk object van deze klasse een job voorstelt met gegeven begin- en eindtijd.

Opmerkingen:

• Let op dat er steeds minstens één job wordt geselecteerd.
• Het is niet toegestaan om de input van de methode selectaan te passen. Indien je dit wel doet, zal de test falen.

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