Siguranta Nationala

Problema se rezolva prin metoda Greedy. Se parcurge in ordinea crescatoare a capetelor stanga tinand 2 variabile Rss si Rsa:

• Rss - tot intervalul [1,Rss] este acoperit de rachete 'sol-sol'
• Rsa - tot intervalul [1,Rsa] este acoperit de rachete 'sol-aer'

La pasul i avem urmatoarele cazuri (presupunem ca Rss ≤ Rsa):

1. B_i ≤ Rss, in acest caz nu conteaza de ce tip va fi considerat intervalul i, deoarece toate punctele din [1,{B_i}] au fost acoperite anterior
2. B_i > Rss, in acest caz intervalul va fi de tip 'sol-aer', iar Rss va primi valoarea B_i.

Din pacate limitare memoriei facea imposibila stocarea intervalelor. Din fericire ele erau deja sortate, deci se puteau preprocesa pe parcursul citirii. De asemenea, cand se stabilea tipul unui interval se afisa in fisierul de iesire.

Astfel algoritmul foloseste O(1) memorie si are complexitatea O(n).