समय के अंतराल की एक सूची को देखते हुए, मुझे अधिकतम गैर-ओवरलैपिंग अंतराल का सेट ढूंढना होगा।अंतराल पेड़ में अधिकतम गैर-ओवरलैपिंग अंतराल
उदाहरण के लिए,
हम निम्न अंतरालों अगर:
[0600, 0830], [0800, 0900], [0900, 1100], [0900, 1130],
[1030, 1400], [1230, 1400]
यह भी है कि समय सीमा दी गई है [0000, 2400]
में रहना होगा।
अंतराल का अधिकतम गैर-ओवरलैपिंग सेट [0600, 0830], [0900, 1130], [1230, 1400]
है।
मैं समझता हूं कि अधिकतम सेट पैकिंग एनपी-पूर्ण है। मैं पुष्टि करना चाहता हूं कि मेरी समस्या (केवल प्रारंभ और समाप्ति समय वाले अंतराल के साथ) एनपी-पूर्ण भी है।
और यदि हां, तो घातीय समय में इष्टतम समाधान खोजने का कोई तरीका है, लेकिन स्मार्ट प्रीप्रोकैसिंग और प्रोनिंग डेटा के साथ। या यदि निश्चित पैरामीटर ट्रैक्टेबल एल्गोरिदम लागू करने के लिए अपेक्षाकृत आसान है। मैं एक अनुमानित एल्गोरिदम के लिए जाना नहीं चाहता।
"अधिकतम" अंतराल के सबसे बड़े _NUMBER_ या अंतराल की सबसे लंबी _total duration_ मतलब यह है? आपका उदाहरण समाधान 6.5 घंटे की कुल अवधि के लिए 3 अंतराल है। यह अधिकतम, 3 या 6.5 बनाता है? –