1. naloga

Sorodstvo

Navdušencu za rodoslovje se je sesula baza podatkov o njegovih prednikih in sorodstvenih povezavah med njimi. Vse, kar je uspel rešiti, so letnice rojstev in smrti posameznih ljudi. Ima torej seznam parov celih števil (ri, si) za i = 1, ..., n, ki povedo, da se je oseba i rodila v letu ri in umrla v letu si. Vrstni red ljudi v seznamu je lahko poljubno premešan, torej ni nujno, da so npr. urejeni po letu rojstva ali kaj podobnega.

Predpostavimo, da je razlika v starosti staršev in otrok vsaj d let (d je neko celo število, večje od 0). Zato bomo rekli, da je oseba j morebitni otrok osebe i natanko tedaj, ko velja ri+d ≤ rj si.

Opiši postopek, ki za dani d in podatke o letih rojstev in smrti (r1, s1), ..., (rn, sn) sestavi najdaljše zaporedje oseb, v katerem velja, da je vsaka naslednja oseba v zaporedju morebitni otrok prejšnje osebe v zaporedju.

Tvoja rešitev naj se ne opira na kakšne realistične predpostavke o tem, kako dolgo ljudje živijo in koliko otrok imajo, saj imajo nekateri uporabniki v svojem rodbinskem drevesu tudi vesoljce, sumerske polbogove in podobna dolgoživa bitja.