Filtraggio degli elementi dell'elenco con la complessità del tempo O (n)

Question

Ho una lista di elementi, in cui ogni elemento è un intervallo intero non negativo. Voglio filtrare l'elenco in modo tale da separare solo i più grandi intervalli non inclusi. E voglio farlo nel modo O(n) con loop singolo. Questo elenco verrà sempre ordinato in base all'intero iniziale di ciascun intervallo. Un elemento intervallo compreso può verificarsi prima o dopo l'elemento intervallo compreso nell'elenco.

Esempio:

Supponiamo lista che ho è {[0-12],[5-15],[5-20],[10-20],[11-30],[25-42],[28-40]}. In questo elenco, gli intervalli [5-15] e [10-20] rientrano nell'intervallo [5-20] quindi è necessario eliminarli. Allo stesso modo l'elemento intervallo [28-40] viene scartato poiché rientra nell'intervallo [25-42]. Voglio fare questo filtraggio usando un singolo ciclo per ottenere la complessità temporale O(n).

Sarebbe possibile raggiungere questo obiettivo? In caso contrario, qual è il modo migliore per filtrare con la complessità più di O(n). Una soluzione in Java sarebbe grandiosa.

Answer 1

Un elemento potrebbe ingoiare quello precedente se hanno lo stesso inizio gamma ma estremità maggiore o uguale. Inoltre, l'elemento potrebbe deglutire dopo se l'intervallo del prossimo termina meno della fine di eleemnt corrente.

Quindi si passa all'elenco e si confrontano gli elementi attuali e successivi.

Se hanno il correnteStart = nextStart e nextEnd> = currentEnd -> remove current.

else Se nextEnd < = currentEnd -> remove next.

Answer 2

in pseudocodice, periodi di fusione può essere fatto così:

def merge(l:list[period], e:period): 
    if l == nil: 
     return list(e) 
    else: 
     lh = l.head 
     ll = l.tail 
     if e.end < lh.start: 
      return e::l // original list prepended with e 
     else if lh.end < e.start: 
      return lh::merge(e,ll) // head + trying to merge period with the tail 
     else: //overlap, make new period from e and list head and merge it with tail 
      newstart = min(e.start, lh.start) 
      newend = max(e.end, lh.end) 
      return merge(period(newstart,newend), ll) 

Nel tuo caso, è necessario diff i/o unione, ma l'idea è simile.