Az eredeti feladat itt.

Megoldás

Először is gondolkodjunk el azon, hogy milyen intervallumokat tartalmaz [a,b]: egész pontosan azokat, amelyek kezdőpontja legalább a, és végpontja legfeljebb b. Arra nincs időnk, hogy végigmenjünk az összes többi intervallumon, hogy leellenőrizzük ezt a feltételt, úgyhogy szükségünk lesz valamiféle adatszerkezetre. Ha kezdőpont szerint lerendezzük az intervallumokat, akkor elég csak az a pontnál, vagy később kezdődőkön végigmenni, de még erre sincs időnk. Hasonló a helyzet, ha végpont szerint rendezünk, és a legkésőbb b-nél befejeződőkön megyünk végig. Valahogy ennek a két halmaznak a metszetét keressük, egész pontosan az elemszámát.

Halmazok metszetét számolni viszont lassú művelet. Itt jön a trükk: számoljuk inkább a komplementer halmaz elemszámát, azaz azon intervallumokat, amelyeket [a,b] nem tartalmaz. Ezek azok, amik a előtt kezdődnek, vagy b után végződnek. A kezdőpont szerinti rendezésből könnyen megállapítható az előbbi típusú intervallumok száma (mondjuk A), a végpont szerinti rendezésből pedig az utóbbiak száma (mondjuk B). És akkor a nem tartalmazott intervallumok száma A+B, vagyis a tartalmazottaké N-1-A-B. Illetve nem, ugyanis csaltam. Ideális esetben már föltűnt, ha nem, akkor most megkeresheted, hogy hol. :)

Szóval ott csaltam, hogy a nem tartalmazott intervallumok száma nem feltétlen A+B, ugyanis lehet, hogy valamelyik intervallumot A-ban és B-ben is megszámoltuk. De ez azt jelenti, hogy az az intervallum tartalmazza [a,b]-t, méghozzá szigorúan (valódi részintervalluma). Emiatt egyrészt nem érdekel minket, hogy mi a pontos érték [a,b] esetén, hiszen az kisebb lesz az őt tartalmazó intervalluménál. De ami fontosabb nekünk, a kapott N-1-A-B érték is kisebb lesz annál, mint amit a nagyobb intervallumnál kapunk. Vagyis elég ezek közül megkeresni a maximumot, és az 1. valóban egy keresett intervallumhoz fog tartozni, és 2. tényleg a tartalmazott intervallumok száma lesz.

Memóriából az intervallumok számával arányos, azaz O(N) elegendő. A futásidőt pedig a rendezés határozza meg, amit természetesen NlogN időben érdemes. Az intervallumhoz tartozó A és B értékeket konstans időben számolhatjuk, ha előtte a rendezett listákon végigmenve letároljuk őket. Összesítve tehát O(NlogN) időben fut az optimális algoritmus.

A bejegyzés trackback címe:

Kommentek:

A hozzászólások a vonatkozó jogszabályok  értelmében felhasználói tartalomnak minősülnek, értük a szolgáltatás technikai  üzemeltetője semmilyen felelősséget nem vállal, azokat nem ellenőrzi. Kifogás esetén forduljon a blog szerkesztőjéhez. Részletek a  Felhasználási feltételekben és az adatvédelmi tájékoztatóban.