Determinare se l'intervallo di date di input si sovrappone a quelli esistenti

Question

Ho una tabella nel database che memorizza items che può essere affittata per un periodo di pochi giorni.

Ora ogni volta che qualcuno affitta un item, specificano un start_date ed un end_date (fondamentalmente un date range per la quale vogliono affittare che item).

Desidero sapere qual è l'algoritmo efficiente (in termini di complessità temporale) per verificare che l'input date range non si sovrapponga a quello esistente date ranges nel database.

Illustrazione:

|<------existing 1------->| 
            |<------existing 2------->| 
       |<------ input date range ---->| (which clearly, overlaps) 

Nota:

Questa domanda non è un duplicato di this domanda. Quello controlla se due date ranges si sovrappongono. La mia domanda riguarda un ingresso date range sovrapposizione con più esistente date ranges

un'altra nota:

Nel caso in cui siete confusi da tag di questa domanda, io sono aperto a entrambi i tipi di risposte, language-agnostic così come language-specific.

Per coloro che vogliono dare language-specific risposta, qui ci sono i dettagli:

Ho un progetto in esecuzione su django 1.9python 3.4 con PostgreSQL come database. I miei modelli sono:

class Item(models.Model): 
    name = models.CharField(max_length=100) 

class BookingPeriod(models.Model): 
    item = models.ForeignKey(Item) 
    start_date = models.DateField() 
    end_date = models.DateField() 

Answer 1

Questa risposta presuppone che tutti gli input precedenti siano legali. In caso contrario, può essere modificato per adattarsi ad altri scenari.

Mantieni due elenchi ordinati nel sistema: uno per lo start date s e uno per lo end date s. Questi elenchi dovranno ovviamente trovare un modo per trovare l'articolo correlato nell'altro elenco. Quando si riceve un nuovo input, trovare il massimo start date che è più piccolo dei nuovi ingressi 'start date e verificare che il relativo end date sia anche più piccolo del nuovo start date, altrimenti il ​​nuovo input non è valido.

Lo stesso vale per lo end date, proprio il contrario.

Penso che questo può essere fatto (usando alberi invece di liste) in O(log n).