Code:
Na brojevnoj pravoj dato je svojim krajevima n intervala. Interval ne sadrži svoje krajnje tacke. Napisati program koji nalazi najveci broj intervala koji se mogu izabrati tako da nemaju zajednickih tacaka.
Ulazni podaci:
U prvom redu standardnog ulaza nalazi se ceo broj n (0 < n <= 5000), broj intervala. U sledecih n redova nalaze se po dva cela broja li i di (-10000 < li < di < 10000) redom levi i desni kraj intervala i (1 <= i <= n ).
Izlaz programa:
Na standardni izlaz ispisati traženi najveci broj intervala koji se mogu izabrati tako da nemaju zajednickih tacaka.
Primer:
Ulaz
4
-1 1
0 5
2 3
5 9
Izlaz
3
Na brojevnoj pravoj dato je svojim krajevima n intervala. Interval ne sadrži svoje krajnje tacke. Napisati program koji nalazi najveci broj intervala koji se mogu izabrati tako da nemaju zajednickih tacaka.
Ulazni podaci:
U prvom redu standardnog ulaza nalazi se ceo broj n (0 < n <= 5000), broj intervala. U sledecih n redova nalaze se po dva cela broja li i di (-10000 < li < di < 10000) redom levi i desni kraj intervala i (1 <= i <= n ).
Izlaz programa:
Na standardni izlaz ispisati traženi najveci broj intervala koji se mogu izabrati tako da nemaju zajednickih tacaka.
Primer:
Ulaz
4
-1 1
0 5
2 3
5 9
Izlaz
3
Moje rjesenje ide ovako (pseudokod).
Svaki interval i ima 3 podatka: A(i) je pocetak, B(i) je kraj, a Q(i) je broj intervala j kojima je B(j) < A(i) (ili laicki receno: Q(i) je broj intervala koji se nalaze prije intervala i, a da nemaju zajednickih tocaka).
Na pocetku svaki interval i ima vrijednost Q(i) postavljenu na 1.
Svrha vrijednosti Q je memoizacija.
Code:
sort intervale po vrijednosti A
for i = 1 to N
for k = 0 to i-1
if (B(k) <= A(i) and Q(k)+1 > Q(i)) Q(i) = Q(k)+1
endfor
if (Q(i) > max) max = Q(i)
endfor
print max
sort intervale po vrijednosti A
for i = 1 to N
for k = 0 to i-1
if (B(k) <= A(i) and Q(k)+1 > Q(i)) Q(i) = Q(k)+1
endfor
if (Q(i) > max) max = Q(i)
endfor
print max
E sad sto tu ne valja? U 10 test primjera samo 2 rade??
NrmMyth, moze pomoc? :)