आपको अंतराल एस का एक सेट दिया गया है। आपको न्यूनतम समय जटिलता

Question

में दिए गए अंतराल (ए, बी) में निहित एस में सभी अंतराल ढूंढना होगा। आपको S अंतराल का एक सेट दिया गया है। आपको S में सभी अंतराल ढूंढना होगा जो न्यूनतम समय जटिलता में दिए गए अंतराल (a, b) में निहित हैं।

यह जानवर बल द्वारा O(n) समय में किया जा सकता है, जहां n सेट S में अंतराल की संख्या है। लेकिन अगर मुझे कुछ प्री-प्रोसेसिंग करने की इजाजत है, तो यह O(n) समय से कम समय में किया जा सकता है। O(log n) समय?

शुरू में मैं interval tree के बारे में सोच रहा था, लेकिन मुझे नहीं लगता कि इसे यहाँ लागू होता है क्योंकि अंतराल पेड़ कि overlaps एक दिया अंतराल के साथ सभी अंतराल प्राप्त करने के लिए प्रयोग किया जाता है है।

Answer 1

आप 2 डी-प्लेन में अपनी समस्या को दोबारा हटा सकते हैं। प्रत्येक अंतराल के (begin, end) को द्वि-आयामी बिंदु होना चाहिए। (ध्यान दें कि सभी वैध अंतराल विकर्ण ऊपर खत्म हो जाएगा)

आपका अंतराल-खोज-समस्या अच्छी तरह से अध्ययन किया ओर्थोगोनल 2 डी रेंज में परिवर्तित हो एल्गोरिदम है या क्रम है, जहां कश्मीर अंकों की संख्या है साथ प्रश्नों की सूचना दी।

Answer 2

Persistent binary search tree का उपयोग यहां किया जा सकता है।

पूर्व प्रसंस्करण:

1. खाली लगातार पेड़ बनाएँ। इसे अपने अंतिम बिंदुओं द्वारा क्रमबद्ध अंतराल को स्टोर करना चाहिए।
2. अपने शुरुआती बिंदुओं से अंतराल को क्रमबद्ध करें।
3. क्रमबद्ध सूची के अंत से शुरू होने वाले प्रत्येक अंतराल के लिए, लगातार पेड़ की "प्रतिलिपि" बनाएं और इस अंतराल को इस प्रतिलिपि में जोड़ें।

खोज:

1. शुरू करने क्रमबद्ध सूची में क्वेरी अंतराल के बिंदु का पता लगाएं।
2. क्वेरी अंतराल के अंत तक सबसे छोटी कुंजी से लगातार पेड़ की "कॉपी" संबंधित Iterate।

खोज समय जटिलता ओ (लॉग (एन) + मीटर) है, जहां मीटर आउटपुट में तत्वों की संख्या है।