Motel
Problema poate fi abordată cu metoda Greedy sau cu algoritmul determinării unui cuplaj maxim. Dar soluţia cea mai eficientă se va obţine folosind heapuri.
Varianta 1
Din păcate, aplicarea metodei Greedy nu conduce la rezultate corecte. Dacă sortăm intervalele solicitate de turişti în ordine crescătoare după ziua care închide intervalul şi sortăm crescător vectorul zilelor specificate de artist, şi parcurgem în paralel cele două şiruri pentru a verifica dacă ziua precizată de artist de pe poziţia i face parte sau nu din intervalul aflat pe aceeaşi poziţie, vom greşi, deoarece pierdem soluţii pentru cazuri de forma următoare:
2
1 4
2 3
1
2
Sortarea după ultima zi din interval ne conduce la
2 3
1 4
1 nu face parte din intervalul [2, 3] şi astfel am ajunge la concluzia că nu avem soluţie, cu toate că ea există:
1 1
2 2
O astfel de rezolvare ar fi obţinut 30 de puncte.
De asemenea, nici varianta când sortăm după extremitatea stângă a intervalelor nu funcţionează corect. Să considerăm de exemplu cazul
1 4
2 3
2
4
Vom atribui intervalului [1, 4] punctul 2 şi astfel punctului 4 nu i se va mai putea atribui intervalul rămas şi iarăşi am ajunge la concluzia că nu există soluţie. Această rezolvare obţine de asemenea 30 de puncte.
Varianta 2
Pentru cei care au cunoştinţe de teoria grafurilor o primă idee ar putea fi construirea unui graf bipartit şi încercarea găsirii unui cuplaj de cardinalitate n. Acest lucru se poate face în complexitate O(n * m) sau O(sqrt(n) * m). În cel mai rău caz m poate ajunge până la n2, dar în practică acest caz este cel mai simplu, pentru că orice cuplare între intervale şi zile duce la soluţie optimă. O implementare eficientă a acestei idei poate obţine între 55 şi 70 de puncte.
Variata 3
O soluţie mult mai simplu de implementat şi care în practică are un timp de rulare asemănător este următoarea: sortăm zilele în care artistul este disponibil în ordine crescătoare. Le parcurgem în această ordine şi atribuim fiecăruia intervalul care are extremitatea din dreapta cea mai mică, dintre intervalele care o cuprind. O implementare naivă va avea complexitatea Θ(n2) şi ar obţine între 55 şi 70 de puncte
Pentru a obţine punctaj maxim vom implementa ideea de mai sus într-un mod mai eficient. Pentru acesta trebuie să cunoaştem structura de date numită min-heap. Criteriul de sortare al heap-ului va fi extremitatea dreaptă a intervalelor.
Sortăm intervalele după extremitatea stângă. La pasul i căutăm intervalul pe care să-l cuplăm cu ziua i. Introducem în heap intervalele încă neintroduse, care cuprind ziua i, după care ştergem din heap intervalele care nu mai cuprind ziua i. Dacă heap-ul devine vid, nu există soluţie, în caz contrar cuplăm ziua i cu intervalul din vârful heap-ului. Complexitate totală: O(n log n).
