Legen Sie fest, ob sich der Eingabedatenbereich mit den vorhandenen Werten überschneidet.

Question

Ich habe eine Tabelle in der Datenbank, die items speichert, die für ein paar Tage gemietet werden kann. Jetzt

, wenn jemand ein item mietet, geben sie ein start_date und ein end_date (im Grunde ein date range, für die sie die item mieten wollen).

Ich möchte wissen, was ist der effiziente Algorithmus (in Bezug auf die zeitliche Komplexität) zu überprüfen, dass der Eingang date range nicht mit bestehenden date ranges in der Datenbank überlappt.

Illustration:

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

Hinweis:

Diese Frage ist nicht ein Duplikat this Frage. Dieser prüft, ob sich zwei date ranges überlappen. Meine Frage ist über einen Eingang date range Überlappung mit mehreren bestehenden date ranges

Noch ein Hinweis:

Falls Sie diese Frage des Tags sind verwirrt, ich bin offen für beide Arten von Antworten, language-agnostic sowie language-specific.

Für diejenigen, die language-specific Antwort geben wollen, sind hier weitere Details:

Ich habe ein django 1.9 Projekt auf python 3.4 mit PostgreSQL als Datenbank. Meine Modelle sind:

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

Diese Antwort setzt voraus, dass alle vorherigen Eingaben zulässig sind. Falls nicht, kann es geändert werden, um anderen Szenarien zu entsprechen.

Halten Sie zwei geordnete Listen in Ihrem System - eine für die start date s und eine für die end date s. Diese Liste muss offensichtlich eine Möglichkeit haben, den korrelierenden Gegenstand in der anderen Liste zu finden. Wenn Sie einen neuen Eingang erhalten, suchen Sie den größten start date, der kleiner ist als die neuen Eingänge start date und prüfen Sie, ob der entsprechende end date auch kleiner ist als der neue start date, andernfalls ist der neue Eingang ungültig.

Gleiches gilt für die end date, genau umgekehrt.

Ich denke, dass dies in O(log n) getan werden kann (mit Bäumen anstelle von Listen).