2013-11-08 18 views
13

समय के अंतराल की एक सूची को देखते हुए, मुझे अधिकतम गैर-ओवरलैपिंग अंतराल का सेट ढूंढना होगा।अंतराल पेड़ में अधिकतम गैर-ओवरलैपिंग अंतराल

उदाहरण के लिए,

हम निम्न अंतरालों अगर:

[0600, 0830], [0800, 0900], [0900, 1100], [0900, 1130], 
[1030, 1400], [1230, 1400] 

यह भी है कि समय सीमा दी गई है [0000, 2400] में रहना होगा।

अंतराल का अधिकतम गैर-ओवरलैपिंग सेट [0600, 0830], [0900, 1130], [1230, 1400] है।

मैं समझता हूं कि अधिकतम सेट पैकिंग एनपी-पूर्ण है। मैं पुष्टि करना चाहता हूं कि मेरी समस्या (केवल प्रारंभ और समाप्ति समय वाले अंतराल के साथ) एनपी-पूर्ण भी है।

और यदि हां, तो घातीय समय में इष्टतम समाधान खोजने का कोई तरीका है, लेकिन स्मार्ट प्रीप्रोकैसिंग और प्रोनिंग डेटा के साथ। या यदि निश्चित पैरामीटर ट्रैक्टेबल एल्गोरिदम लागू करने के लिए अपेक्षाकृत आसान है। मैं एक अनुमानित एल्गोरिदम के लिए जाना नहीं चाहता।

+0

"अधिकतम" अंतराल के सबसे बड़े _NUMBER_ या अंतराल की सबसे लंबी _total duration_ मतलब यह है? आपका उदाहरण समाधान 6.5 घंटे की कुल अवधि के लिए 3 अंतराल है। यह अधिकतम, 3 या 6.5 बनाता है? –

उत्तर

23

यह एक एनपी-पूर्ण समस्या नहीं है। मैं इस समस्या को हल करने के लिए गतिशील प्रोग्रामिंग का उपयोग कर O(n * log(n)) एल्गोरिदम के बारे में सोच सकता हूं।

मान लीजिए कि हमारे पास अंतराल है। मान लें कि दी गई रेंज S है (आपके मामले में, S = [0000, 2400])। या तो मान लें कि सभी अंतराल S के भीतर हैं, या रैखिक समय में S के भीतर नहीं सभी अंतराल को खत्म करें।

  1. पूर्व प्रक्रिया:

    • सब क्रमबद्ध उनके शुरू अंक के अंतराल। मान लें कि हमें एन अंतराल के A[n] एक सरणी मिलती है।
      • यह कदम लेता है O(n * log(n)) समय
    • अंतराल के सभी अंत अंक के लिए, छोटी से छोटी के सूचकांक को खोजने का कहना है कि इसके बाद इस प्रकार शुरू करते हैं। मान लीजिए कि हमें n पूर्णांक के Next[n] का सरणी मिलती है।
      • अगर इस तरह के बिंदु शुरू अंतराल i, के अंत बिंदु के लिए मौजूद नहीं है हम Next[i] करने के लिए n असाइन कर सकते हैं।
      • हम सभी अंतराल के एन एंड पॉइंट्स को समझाकर O(n * log(n)) समय में ऐसा कर सकते हैं, और उत्तर खोजने के लिए बाइनरी खोज का उपयोग कर सकते हैं। हो सकता है कि इसे हल करने के लिए रैखिक दृष्टिकोण मौजूद हो, लेकिन इससे कोई फर्क नहीं पड़ता, क्योंकि पिछला चरण पहले से ही O(n * log(n)) समय लेता है।
  2. डी पी:

    • मान लीजिए अधिकतम गैर-अतिव्यापी अंतराल रेंज में [A[i].begin, S.end]f[i] है। फिर f[0] वह उत्तर है जिसे हम चाहते हैं।
    • इसके अलावा f[n] = 0 लगता है;
    • राज्य संक्रमण समीकरण:
      • f[i] = max{f[i+1], 1 + f[Next[i]]}
    • यह काफी स्पष्ट है कि डी पी कदम रैखिक समय लेने के लिए है।

ऊपर समाधान एक मैं इस समस्या की पहली नज़र में साथ आने के लिए है।

(समान संकेतन और इसके बाद के संस्करण डीपी दृष्टिकोण के रूप में मान्यताओं के साथ)

  1. : उसके बाद, मैं भी एक लालची दृष्टिकोण है जो सरल (बड़ा हे संकेतन के अर्थ में, लेकिन तेजी से नहीं है) बाहर लगता है पूर्व-प्रक्रिया: सभी अंतराल को उनके अंत अंक से क्रमबद्ध करें। मान लें कि हमें एन अंतराल के B[n] एक सरणी मिलती है।

  2. लालची:

    int ans = 0, cursor = S.begin; 
    for(int i = 0; i < n; i++){ 
        if(B[i].begin >= cursor){ 
         ans++; 
         cursor = B[i].end; 
        } 
    } 
    

ऊपर दो समाधान मेरे मन से बाहर आते हैं, लेकिन आपकी समस्या को भी गतिविधि चयन समस्या, विकिपीडिया http://en.wikipedia.org/wiki/Activity_selection_problem पर पाया जा सकता है के रूप में जाना जाता है।

इसके अलावा, एल्गोरिदम का परिचय इस समस्या को 16.1 में गहराई से चर्चा करता है।

+1

मैं बिंदु 2 की दूसरी बुलेट पर थोड़ा उलझन में हूं। क्या आप कह रहे हैं कि हमें अगले संभावित अंतराल की एक नई सरणी बनाने की आवश्यकता है? क्या यह 'अगला [एन] 'है, या' अगला [एन] == ए [एन]' है? शायद आप स्पष्टीकरण के लिए कुछ और कोड लिख सकते हैं? –

संबंधित मुद्दे