ओवरलैपिंग नौकरियों का सबसे छोटा सेट खोजें

Question

एक दोस्त ने मुझे एक पहेली दी है जिसे वह कहता है कि ओ (एन^3) समय से बेहतर में हल किया जा सकता है।

एन नौकरियों के एक सेट को देखते हुए प्रत्येक के पास एक सेट स्टार्ट टाइम और एंड टाइम होता है (ओवरलैप बहुत संभव है), सबसे छोटे सबसेट को ढूंढें कि प्रत्येक नौकरी के लिए या तो नौकरी शामिल है या उस नौकरी के साथ ओवरलैप है।

मुझे पूरा यकीन है कि इष्टतम समाधान सबसे अनजान ओवरलैप के साथ नौकरी चुनना है, इसे समाधान सेट में जोड़ें, फिर इसे चिह्नित करें, और इसके ओवरलैप करें। और तब तक दोहराएं जब तक सभी नौकरियां चिह्नित न हों।
यह पता लगाने के लिए कि कौन सी नौकरी सबसे अनमार्कित ओवरलैपर्स है, एक साधारण आसन्नता मैट्रिक्स (ओ (एन^2)) है, और प्रत्येक बार नौकरी का चयन करने के लिए इसे फिर से चालू किया जाना चाहिए, अंक अपडेट करने के लिए, इसे ओ (एन^3)।

क्या कोई बेहतर समाधान है?

Answer 1

A नौकरियों का सेट बनें जिन्हें हमने अभी तक ओवरलैप नहीं किया है।

1. A जो कम से कम अंत समय (t) है में काम x का पता लगाएं।
2. उन सभी नौकरियों से जिनके प्रारंभ समय t से कम है: अधिकतम अंत समय के साथ j नौकरी चुनें।
3. आउटपुट सेट में j जोड़ें।
4. से j ओवरलैप करने वाली सभी नौकरियों को हटाएं।
5. 1-4 से A दोहराएं खाली है।

ओ (एन^2) में एक सरल कार्यान्वयन चलाया जाएगा। interval trees का उपयोग करना संभवतः O (n * logn) में हल करना संभव है।

यह एक आदर्श समाधान क्यों है (औपचारिक प्रमाण नहीं) के पीछे मूल विचार: हमें एक नौकरी चुननी है जिसका प्रारंभ समय t से कम है, ताकि x ओवरलैप हो जाए। अगर हम S को उन सभी नौकरियों का सेट बनें जिनके प्रारंभ समय t से कम है, तो यह दिखाया जा सकता है कि jS, और संभवतः अधिक में किसी भी नौकरी के समान नौकरियों को ओवरलैप कर देगा। चूंकि हमें S में एक नौकरी चुननी है, तो सबसे अच्छी पसंद j है। हम इस विचार का उपयोग नौकरियों की संख्या में शामिल होने से सबूत बनाने के लिए कर सकते हैं।

Answer 2

हम एक गतिशील प्रोग्रामिंग दृष्टिकोण के साथ एक ओ (nlogn) समाधान प्राप्त कर सकते हैं। विशेष रूप से, हम के ^वें नौकरी सहित सबसे छोटे सेट के आकार पर विचार करना चाहते हैं और पहले k नौकरियों (प्रारंभ समय द्वारा आदेशित) से मेल खाते हैं, जिसे हम S(k) द्वारा दर्शाते हैं। हमें पहले एक सहायक नौकरी (∞, ∞) जोड़नी चाहिए, इसलिए परिणाम इस अंतिम नौकरी के लिए हमारा डीपी समाधान होगा।

S(k) की गणना करने के लिए, p(k) पर काम करें जो k नौकरी से पहले समाप्त होता है, लेकिन अधिकतम प्रारंभ समय होता है। ध्यान दें कि p एक बढ़ता हुआ कार्य है। S(k)end(i) > start(p(k)) के साथ न्यूनतम S(i) से अधिक होगा।

हम संभावित नौकरियों के ढेर को (S(k) आदेशित न्यूनतम) बनाए रखने के द्वारा कुशलता से यह नौकरी ढूंढ सकते हैं। प्रत्येक S(k) की गणना करने के बाद, हम नौकरी को ढेर में जोड़ते हैं।जब हम नौकरी प्राप्त करना चाहते हैं, तो हम ढेर के आधार पर नौकरियों को हटाते हैं जो बहुत जल्दी खत्म होते हैं, जब तक कि हम एक उपयुक्त नहीं पाते। यह कुल ओ (nlogn) में कुल ले जाएगा, क्योंकि हम प्रत्येक हीप ऑपरेशन (पॉप/पीक/पुश) के अधिकांश ओ (एन) में करते हैं।

कार्य का शेष p(k) मानकों को कुशलतापूर्वक गणना करना है। ऐसा करने का एक तरीका है कि सभी नौकरी शुरू करने और समाप्त होने पर (बढ़ते समय में), नवीनतम शुरुआती नौकरी का ट्रैक रखें।