== include(page="template/taskheader" task_id="senzori") ==

De-a lungul autostrazii Soarelui sunt amplasati $N$ senzori, numerotati in ordinea de la Bucuresti spre Constanta, de la $1$ la $N$. In timpul unei zile, senzorii inregistreaza date in continuu, cu exceptia unui anumit interval de timp; mai exact, pentru orice senzor $i$ exista un interval $[T{~1,i~},T{~2,i~})$ in care senzorul trebuie sa trimita datele inregistrate catre statia centrala (acest interval de timp poate fi diferit de la un senzor la altul). Durata de transmitere a datelor senzorului $i$ este $d{~i~}$, iar datele trebuie sa fie transmise intr-un interval de timp $[t{~start,i~},t{~start,i~}+d{~i~}) &sube; [T{~1,i~},T{~2,i~})$ (momentul $t{~start,i~}$ nu este dat). Datele unui senzor $i$ au o valoare $v{~i~}$ (in functie de importanta strategica a amplasarii senzorului). Senzorii comunica wireless cu statia centrala, pe aceeasi frecventa, si de aceea pot aparea interferente la transmisia datelor senzorilor cu numere de ordine consecutive. Asadar, intervalele de timp in care sunt transmise datele a doi senzori $i$ si $i+1$ $(1&le;i<N)$ trebuie sa fie disjuncte: $[t{~start,i~},t{~start,i~}+d{~i~}) &cap; [t{~start,i+1~},t{~start,i+1~}+d{~i+1~}) = &empty;$. Aceasta restrictie poate conduce la situatia neplacuta in care nu toti senzorii vor putea trimite datele catre statia centrala in intervalul de timp disponibil ( $[T{~1,i~},T{~2,i~})$ pentru senzorul $i$). In acest caz, se doreste determinarea unei submultimi de senzori care vor transmite datele catre statia centrala si pentru care suma valorilor datelor transmise este maxima.

De-a lungul autostrazii Soarelui sunt amplasati $N$ senzori, numerotati in ordinea de la Bucuresti spre Constanta, de la $1$ la $N$. In timpul unei zile, senzorii inregistreaza date in continuu, cu exceptia unui anumit interval de timp; mai exact, pentru orice senzor $i$ exista un interval $[T{~1,i~},T{~2,i~})$ in care senzorul trebuie sa trimita datele inregistrate catre statia centrala (acest interval de timp poate fi diferit de la un senzor la altul). Durata de transmitere a datelor senzorului $i$ este $d{~i~}$, iar datele trebuie sa fie transmise intr-un interval de timp $[t{~start,i~},t{~start,i~}+d{~i~}) ⊆ [T{~1,i~},T{~2,i~})$ (momentul $t{~start,i~}$ nu este dat).
Datele unui senzor i au o valoare vi (în funcţie de importanţa strategică a amplasării senzorului). Senzorii comunică wireless cu staţia centrală, pe aceeaşi frecvenţă, şi de aceea pot apărea interferenţe la transmisia datelor senzorilor cu numere de ordine consecutive. Aşadar, intervalele de timp în care sunt transmise datele a doi senzori i şi i+1 (1≤i<N) trebuie să fie disjuncte:
[tstart,i,tstart,i+di) [tstart,i+1,tstart,i+1+di+1)=
Această restricţie poate conduce la situaţia neplacută în care nu toţi senzorii vor putea trimite datele către staţia centrală în intervalul de timp disponibil ([T1,i,T2,i) pentru senzorul i). În acest caz, se doreşte determinarea unei submulţimi de senzori care vor transmite datele către staţia centrală şi pentru care suma valorilor datelor transmise este maximă.

h2. Date de intrare