क्या अधिकांश संघर्षों के साथ लालच से अंतराल को अंतराल शेड्यूलिंग हल करता है?

Question

हम समय-निर्धारण की समस्या है, जिसमें हम, निरंतर अंतराल है कि कोई ओवरलैप कर का सबसे बड़ा सेट का चयन करना होगा एक लालची एल्गोरिथ्म के साथ हल कर सकते हैं: हम सिर्फ अंतराल कि जल्द से जल्द खत्म हो उठा रखें: जाहिर है http://en.wikipedia.org/wiki/Interval_scheduling

, लालच से उठा कम से कम संघर्ष के साथ अंतराल काम नहीं करता है।

मैं सोच रहा था कि सभी अंतराल को एक बड़े सेट में डालने और फिर अंततः अंतराल को हटाए जाने वाले अधिकांश संघर्षों के साथ अंतराल को हटा दिया जाता है (जब तक अंतराल में कोई संघर्ष नहीं होता) काम करता है। मैं प्राथमिकता कतार के साथ इस लालची एल्गोरिदम को कार्यान्वित करने की कल्पना कर सकता हूं: हर बार जब हम प्राथमिकता कतार से सबसे बड़े संघर्षों के साथ अंतराल एक्स को हटाते हैं, तो हम अंतराल एक्स के साथ संघर्ष करने के लिए उपयोग किए जाने वाले अन्य अंतराल को अपडेट करते हैं ताकि अन्य अंतराल को अब 1 के रूप में चिह्नित किया जा सके। कम संघर्ष

क्या यह काम करता है? मैं इसे अस्वीकार करने के लिए एक counterexample के साथ आने की कोशिश कर रहा हूँ और नहीं कर सकता।

Answer 1

यहां एक काउंटररेक्स नमूना है। विचार सबसे पहले पिक पर एक आवश्यक अंतराल ड्रॉप करना है। विवादों की संख्या दाईं ओर है।

 ==== 2 
     ----  3 
     ----  3 
    ====  4 
    ----   3 
----   3 
====   2 

जाहिर है, हम तीन बोल्ड (====) अंतराल लेने और ड्रॉप चार पतली() अंतराल चाहते हैं। तीन गैर-अंतरण अंतराल प्राप्त करने का कोई और तरीका नहीं है।

वैसे, आपको TopCoder tutorial लालची समस्याओं पर दिलचस्प लग सकता है क्योंकि यह एक ही समस्या पर कई दृष्टिकोणों की चर्चा के साथ शुरू होता है।