पायथन में जांचें कि कोई अंतराल दूसरे को पूरी तरह ओवरलैप करता है या नहीं

मान लीजिए हमें अंतरालों का एक समूह दिया गया है जिसमें मान (a, b) होते हैं, जहां a किसी घटना का प्रारंभ समय दर्शाता है और b समाप्ति समय। हमारा कार्य यह जांचना है कि क्या इनमें से कोई भी अंतराल इस समूह में किसी अन्य अंतराल को पूरी तरह से ओवरलैप करता है। यदि कोई अंतराल ओवरलैप करता है, तो हम True लौटाते हैं, अन्यथा False।

उदाहरण के लिए, यदि इनपुट [(4,6), (10,12), (7,9), (13,16)] है, तो आउटपुट False होगा। यदि इनपुट [(4,6), (4,9), (7,11), (5,8)] है, तो आउटपुट True होगा।

समाधान दृष्टिकोण

अंतरालों को सॉर्ट करके, हम आसानी से जांच सकते हैं कि कोई अंतराल पिछले अंतराल के भीतर पूरी तरह से समाहित है या नहीं।

एल्गोरिदम चरण:

1. अंतरालों की सूची को सॉर्ट करें (डिफ़ॉल्ट रूप से पहले तत्व के अनुसार, फिर दूसरे के अनुसार)
2. सूची में दूसरे अंतराल से शुरू करके प्रत्येक अंतराल के लिए:
• यदि वर्तमान अंतराल का अंत (intervals[i][1]) पिछले अंतराल के अंत (intervals[i-1][1]) से कम या बराबर है, तो इसका मतलब है कि वर्तमान अंतराल पिछले अंतराल के भीतर पूरी तरह से समाहित है
• ऐसे मामले में True लौटाएं
3. यदि लूप पूरा होने पर कोई ऐसा ओवरलैप नहीं मिला, तो False लौटाएं

पायथन कार्यान्वयन

def solve(intervals):
    intervals.sort()
    for i in range(1, len(intervals)):
        if intervals[i][1] <= intervals[i-1][1]:
            return True
    return False

intervals1 = [(4,6), (10,12), (7,9), (13,16)]
intervals2 = [(4,6), (4,9), (7,11), (5,8)]
print(solve(intervals1))  # False
print(solve(intervals2))  # True

इनपुट

[(4,6),(10,12),(7,9),(13,16)] 
[(4,6), (4,9), (7,11), (5,8)]

आउटपुट

False True

व्याख्या:

दूसरे उदाहरण में, अंतराल (5,8) पूरी तरह से (4,9) के भीतर समाहित है, इसलिए फ़ंक्शन True लौटाता है।