Come identificare il numero massimo di intervalli di date sovrapposti?

Questa domanda potrebbe essere simile a:

  • Determinare se due intervalli di date si sovrappongono
  • Confronto dell’intervallo di date multiple per la sovrapposizione: come farlo in modo efficiente?

Ma come posso ottenere il numero massimo di intervalli di date sovrapposti? (preferibilmente in C #)

Esempio: (da – a)

01/01/2012 - 10/01/2012 03/01/2012 - 08/01/2012 09/01/2012 - 15/01/2012 11/01/2012 - 20/01/2012 12/01/2012 - 14/01/2012 

Risultato = 3 intervalli di date che si sovrappongono al massimo

Soluzione : ansible implementazione della soluzione proposta da @AakashM

 List<Tuple> myTupleList = new List<Tuple>(); foreach (DataRow row in objDS.Tables[0].Rows) // objDS is a DataSet with the date ranges { var myTupleFrom = new Tuple(DateTime.Parse(row["start_time"].ToString()), 1); var myTupleTo = new Tuple(DateTime.Parse(row["stop_time"].ToString()), -1); myTupleList.Add(myTupleFrom); myTupleList.Add(myTupleTo); } myTupleList.Sort(); int maxConcurrentCalls = 0; int concurrentCalls = 0; foreach (Tuple myTuple in myTupleList) { if (myTuple.Item2 == 1) { concurrentCalls++; if (concurrentCalls > maxConcurrentCalls) { maxConcurrentCalls = concurrentCalls; } } else // == -1 { concurrentCalls--; } } 

Dove maxConcurrentCalls sarà il numero massimo di intervalli di date simultanei.

  • Per ogni intervallo, crea due Tuple s con valori start, +1 e end, -1
  • Ordina la raccolta di tuple per data
  • Scorrere l’elenco ordinato, aggiungendo la parte numero della tupla a un totale parziale e tenendo traccia del valore massimo raggiunto dal totale parziale
  • Restituisce il valore massimo raggiunto dal totale parziale

Esegue in O(n log n) causa dell’ordinamento. C’è probabilmente un modo più efficiente.