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 mutueel compatibele jobs te selecteren.

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.

Opgave

Schrijf een Python-functie selecteer die een lijst van taken als parameter krijgt, en die het aantal geselecteerde taken evenals de lijst van geselecteerde taken teruggeeft.

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

>>> selecteer([('a', 0, 6), ('b', 1, 4), ('c', 3, 5), ('d', 3, 8), ('e', 4, 7), ('f', 5, 9), ('g', 6, 10), ('h', 8, 11)])
(3, [('b', 1, 4), ('e', 4, 7), ('h', 8, 11)])

>>> selecteer([('A', 1, 16), ('B', 24, 29), ('C', 8, 22), ('D', 4, 19), ('E', 30, 42), ('F', 35, 50), ('G', 8, 16), ('H', 4, 17), ('I', 9, 11)])
(3, [('B', 24, 29), ('E', 30, 42), ('I', 9, 11)])