Algoritmo per la ricerca di tempi di sovrapposizione

1. Includere tutti i punti di inizio e fine (nel tempo) dei lavori in un array (ciò crea 2 * elementi N (1 per inizio 1 per fine))
2. ordina l'ordinamento dell'array per il timestamp dell'evento,

3. quindi itera sugli elementi (2 * N) come segue:

   for each element X 
   do 
     if(X.type == start)
       counter++
     else
       counter--
     ans=max(ans, counter);
   end
   

Complessità : O (n.log (n)) per la creazione iniziale della struttura ordinata + O (n) per l'iterazione attraverso i suoi elementi.

Modifica: è stato suggerito da Giorgio che viene utilizzato un array, che è un'opzione migliore. (In origine il suggerimento era di usare un albero rosso / nero, ma sembra che non sia necessaria alcuna funzione di rimozione delle attività, quindi mantenere l'ordine è banale).

SQL sa come ordinare le cose, e scommetto che il tuo motore usa l'algoritmo più efficiente che può (cioè O(n log(n)) ), mentre funziona ancora se il set di risultati non si adatta alla RAM (in contrasto con K. La risposta di Steff che fallirà se l'array non si adatta alla RAM). In python:

import sqlite3
connection = sqlite3.connect("database.db")
cursor = connection.cursor()
cursor.execute("SELECT isStart from (" +
               "  SELECT startTime AS time, 1 AS isStart FROM myTable " +
               "  UNION ALL " +
               "  SELECT endTime as time, -1 AS isStart FROM myTable " +
               "  ORDER BY time ASC, isStart ASC" +
               ")")
maxOverlap = 0
currentOverlap = 0
for (isStart,) in cursor:
    currentOverlap += isStart
    maxOverlap = max(maxOverlap, currentOverlap)
print maxOverlap

Nota che l'ordine isStart ASC è necessario, quindi gli intervalli [10,15] e [15,23] non sono considerati sovrapposti.

Per ulteriori miglioramenti, è probabilmente il caso che le colonne startTime e endTime abbiano un indice, quindi il motore SQL dovrebbe unire efficientemente le due tabelle già ordinate, risultando in un'operazione O(n) (il fattore O(log(n)) allora succede al momento dell'inserimento per ogni riga, quando viene aggiunto all'indice, ma lo hai già in ogni caso). Se il tuo motore SQL non è abbastanza intelligente da fare un'unione efficiente, fallo da solo al volo (ancora in python):

import sqlite3
connection = sqlite3.connect("database.db")
cursorStart = connection.cursor()
cursorStart.execute("SELECT startTime FROM myTable ORDER BY startTime ASC")
cursorEnd = connection.cursor()
cursorEnd.execute("SELECT endTime FROM myTable ORDER BY endTime ASC")
maxOverlap = 0
currentOverlap = 0
currentStart = cursorStart.fetchone()
currentEnd = cursorEnd.fetchone()
while currentStart is not None and currentEnd is not None:
    if currentStart < currentEnd:
        currentOverlap += 1
        currentStart = cursorStart.fetchone()
    else:
        currentOverlap -= 1
        currentEnd = cursorEnd.fetchone()
    maxOverlap = max(maxOverlap, currentOverlap)
print maxOverlap