abbiamo uno spazio 1-d [1 ... N]. Ci vengono dati intervalli M della forma [L (i), R (i), C (i)] per 1 < = i < = M, dove L (i) è il punto più a sinistra, R (i) il più a destra e C (i) il valore di tale intervallo.
Ora, per ogni punto da 1 a N dello spazio 1-d, dobbiamo trovare se il punto si trova in un intervallo. Se lo fa, allora dobbiamo trovare l'intervallo con il valore minimo.
Ho un algoritmo O ((N + M) logM molto semplice. Fondamentalmente, manteniamo un multiset. Il valore migliore per il punto i è il minimo del multiset. Scopriamo anche se il punto si trova in un intervallo utilizzando due vettori ausiliari di valori di costo. Il primo è per i valori di costo che devono essere inseriti nel multiset, il secondo è per i valori di costo che devono essere rimossi. Usiamo il multiset perché i valori di costo possono essere duplicati.
Totale complessità = >
N * logM (per ogni punto, dobbiamo trovare il minimo da un multiset e può essere fatto in logM, quindi N * logM)
+ MlogM (valori M da inserire in totale per un totale di intervalli M)
+ MlogM (valori M da rimuovere in totale per un totale di intervalli M)
= > NlogM + 2MlogM = > (N + M) logM
Quindi, spero in un algoritmo migliore (N + M) forse. Quindi, c'è qualche idea / algoritmo interessante per questo problema?
