कहें [ए, बी] एक बी से वास्तविक रेखा पर अंतराल का प्रतिनिधित्व करता है, < बी, समावेशी (यानी, [ए, बी] = सभी एक्स का सेट जैसे कि < = x < = b)। इसके अलावा, [ए, बी] और [सी, डी] 'ओवरलैपिंग' हैं यदि वे किसी भी एक्स को साझा करते हैं जैसे एक्स दोनों [ए, बी] और [सी, डी] में है।अंतराल की सूची में अंतराल ओवरलैप के लिए खोज?
अंतराल की एक सूची को देखते हुए, ([x1, y1], [x2, y2], ...), [x, y] के साथ ओवरलैप होने वाले सभी अंतराल को खोजने का सबसे प्रभावी तरीका क्या है?
जाहिर है, मैं प्रत्येक को आजमा सकता हूं और इसे ओ (एन) में प्राप्त कर सकता हूं। लेकिन मैं सोच रहा था कि क्या मैं कुछ चालाक तरीके से अंतराल की सूची को सॉर्ट कर सकता हूं, मैं एक बाइनरी खोज के माध्यम से ओ (लॉग एन) में आइटम/एक/ओवरलैपिंग आइटम ढूंढ सकता हूं, और फिर सूची में उस स्थिति से 'चारों ओर देखो' ढूंढ सकता है सभी ओवरलैपिंग अंतराल। हालांकि, मैं अंतराल को कैसे क्रमबद्ध करूं ताकि ऐसी रणनीति काम करेगी?
ध्यान दें कि सूची आइटमों में तत्वों के बीच ओवरलैप हो सकते हैं, जो कि यह कठिन बनाता है।
मैंने अंतराल को अपने बाएं छोर, दाएं अंत, मध्य से क्रमबद्ध करके कोशिश की है, लेकिन कोई भी संपूर्ण खोज का कारण नहीं लग रहा है।
सहायता?
+1 क्योंकि यह मेरे कामकाजी दिन को और अधिक रोचक बना देता है। –