Problema: ti vengono assegnati n lavori, ognuno dei quali ha un inizio e un orario di fine. L'attività consiste semplicemente nel generare il numero massimo di lavori attivi (quelli che si sovrappongono tra loro, inclusi) e restituire l'intervallo di tempo dei lavori che si sovrappongono.
Ad esempio (formato: lavoro = inizio, fine):
J1 = 0, 1
J2 = 1, 1.2
J3 = 2, 2.5
J4 = 0.3, 0.7
J5 = 1.5, 2
J6 = 0.5, 1
Avrebbe due intervalli sovrapposti:
0 to 1.2, with four jobs (J1, J2, J4, J6)
1.5 to 2.5 with two jobs (J3, J5)
Il primo intervallo di sovrapposizione sarebbe la soluzione: 4 lavori sovrapposti con un intervallo di tempo compreso tra 0 e 1.2.
Come puoi vedere, l'input può o non può essere ordinato, il che è problematico per motivi di prestazioni. Mi chiedo se ci sia un algoritmo standard per questo problema perché mi viene data una stringa molto grande che devo elaborare e trovare lavori che si sovrappongono.
Il mio attuale approccio è di trattarlo come un problema online, e quindi di leggere l'ora di inizio e di fine, quindi memorizzarlo in una mappa di hash, e in seguito solo leggere il resto degli input e se cade in un intervallo esistente, aggiungere per i valori, quindi modifica l'ora di fine se l'ora di fine è maggiore dell'ora di fine precedente.
Sono sulla buona strada? Grazie mille.