निर्धारित करें कि इनपुट दिनांक सीमा मौजूदा लोगों के साथ ओवरलैप है

Question

मेरे पास डेटाबेस में एक तालिका है जो items स्टोर करती है जिसे कुछ दिनों की अवधि के लिए किराए पर लिया जा सकता है।

अब जब भी किसी एक item किराए, वे निर्दिष्ट एक start_date और एक end_date (मूल रूप से एक date range जिसके लिए वे किराए के लिए है कि item चाहते हैं)।

मैं जानना चाहता हूं कि इनपुट date range डेटाबेस में मौजूदा date ranges के साथ ओवरलैप नहीं है, यह जानने के लिए कुशल एल्गोरिदम (समय जटिलता के मामले में) क्या है।

उदाहरण:

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

नोट:

यह सवाल this सवाल का डुप्लिकेट नहीं है। वह जांचता है कि दो date ranges ओवरलैप है या नहीं। मेरा प्रश्न के साथ कई मौजूदा date ranges

एक और नोट एक इनपुट date range अतिव्यापी के बारे में है:

मामले में आप इस सवाल के टैग से उलझन में कर रहे हैं, मैं जवाब के दोनों प्रकार, language-agnostic रूप में अच्छी तरह language-specific के रूप में करने के लिए खुला रहा हूँ।

मैं एक django 1.9 परियोजना PostgreSQL डेटाबेस के रूप में साथ python 3.4 पर चल रहे हैं:

जो लोग language-specific जवाब देने के लिए, यहां और विवरण हैं। मेरे मॉडल हैं:

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

यह उत्तर मानता है कि पिछले सभी इनपुट कानूनी हैं। यदि नहीं, तो इसे अन्य परिदृश्यों में फिट करने के लिए बदला जा सकता है।

अपने सिस्टम में दो आदेशित सूचियां रखें - start date एस और end date एस के लिए एक। इन सूचीओं को स्पष्ट रूप से अन्य सूची में सहसंबंधित वस्तु को खोजने का एक तरीका होगा। नया इनपुट प्राप्त करते समय, सबसे बड़ा start date खोजें जो नए इनपुट 'start date से छोटा है और यह जांचें कि प्रासंगिक end date नए start date से भी छोटा है, अन्यथा नया इनपुट अवैध है।

end date के लिए ही जाता है, बस दूसरी तरफ।

मुझे लगता है कि यह O(log n) में किया जा सकता है (सूचियों के बजाय पेड़ का उपयोग कर)।