Problema di calcolo degli intervalli di date sovrapposti

Ho riscontrato un problema nel tentativo di elaborare l'algoritmo corretto per calcolare un insieme di intervalli di date.Problema di calcolo degli intervalli di date sovrapposti

Fondamentalmente ho un elenco di intervalli di date non ordinati (Elenco contenente matrici di inizio e fine ore) e voglio consolidare questo elenco in modo che non contenga tempi di sovrapposizione.

Fondamentalmente per consolidare due intervalli di date:

if start1 <= end2 and start2 <= end1 //Indicates overlap 
    if start2 < start1 //put the smallest time in start1 
     start1 = start2 
    endif 
    if end2 > end1 //put the highest time in end1 
     end1 = end2 
    endif 
endif

Questo unisce i due volte data.

Ho colpito un ostacolo quando si tratta di iterare attraverso tutti i valori in modo che l'elenco di fine contenga solo valori che non si sovrappongono.

La mia programmazione funzionale e ricorsiva è un po 'arrugginita e qualsiasi aiuto sarebbe benvenuto.

fonte

2011-09-19 emt14

http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844 contiene una soluzione con spiegazione per questo (beh, dipende da cosa si sta ottimizzando, non è stato specificato quella..). dovrebbe essere molto facile da implementare in FP –

Qualche possibilità che potresti mettere nella giusta direzione su quale algoritmo, struttura dei dati o approccio ti stai riferendo? – emt14

Penso che sia all'inizio nella sezione algoritmi greedy (anche se non sono sicuro). devi prima ordinare la lista. –

Non guardare gli intervalli, guardare solo alle loro estremità.

Hai un sacco di momenti iniziali e un sacco di momenti finali. Immagina che i momenti iniziali siano rossi e che i momenti finali siano blu. Oppure immagina che i momenti iniziali stiano aprendo le parentesi e che i momenti finali stiano chiudendo le parentesi graffe.

Metti tutti insieme in un elenco. Ordina la lista dalla più recente alla più recente, ignorando il colore.

Ora prendi un contatore impostato su zero con te e cammina lungo l'elenco. Quando vedi un momento rosso, incrementa il contatore. Quando vedi un momento blu, decrementa il contatore. Quando il valore del contatore passa da 0 a 1, emettere "start" e l'ora corrente. Quando il valore del contatore passa da 1 a 0, emette "fine" e l'ora corrente. Se il valore del contatore scende sotto 0, uscita "Houston, abbiamo un problema". Dovresti finire con il tuo contatore a 0 e una serie di piacevoli intervalli non sovrapposti.

Questo è il buon vecchio algoritmo di conteggio delle parentesi.

Illustrazione.

A bunch of overlapping intervals: 

(-------------------) 
         (----------------------)   
                  (---) 
     (---------------------)      
                (-----------------) 

A bunch of interval ends: 

(-----(-------------)-(-----)----------------)  (----(---)--------)

fonte

2011-09-19 10:15:37

Funziona a meraviglia e molto semplice da implementare. Grazie, non penso che stavo andando nella giusta direzione! – emt14

Questo algoritmo ha funzionato alla perfezione per un problema diverso che avevo nel contare l'assegnazione delle risorse in un sistema di prenotazione. L'obiettivo era di iniziare con un numero fisso di alcune risorse e determinare se qualcuno potesse verificare o riservare un sottoinsieme del totale dato che altri avevano già fatto lo stesso. – agent154

risposta di n.m. è tutto il necessario, ma se si desidera utilizzare il codice che hai già fatto poi semplicemente ordinare gli intervalli per il momento di inizio e camminare attraverso la lista la fusione sovrapposizioni.

fonte

2011-09-19 10:32:16 quasiverse

Problema di calcolo degli intervalli di date sovrapposti

risposta

Problemi correlati