turrets - solutie

( data de Mugurel Ionut Andreica )

	Se sorteaza capetele intervalelor si pentru fiecare se memopreaza tipul lui (stanga sau dreapta). Daca exista vreun interval inclus in intervalul [0,L] care sa fie inclus doar intr-unul din cele N intervale specificate, atunci nu exista solutie. Altfel:

-> primul interval va fi de tip "Missile"

	Am ajuns la captul din stanga al unui interval si stim ca pana acum, intervalul [0,A] a fost acoperit de 'Missiles' si [0,B] de Laser. Presupunem A<=B. Si fie CD capatul din dreapta al intervalului tocmai deschis (intervalele se deschid in ordinea sortata a capetelor-stanga). Daca CD<=A, atunci nu conteaza ce tip va avea acest interval (nu va schimba nimic). Altfel, tipul intervalului va fi 'Laser', iar B va deveni CD (asadar, tipul unui nou interval deschis va fi cel pentru care intervalul de acoperire pana la deschiderea intervalului respectiv este mai scurt) => algoritmul este de tip GREEDY