अस्वीकरण: नीचे वर्णित विधि सार्वभौमिक नहीं है, लेकिन यह अक्सर समस्या का समाधान कर सकती है या आपको सही समाधान तक पहुंचने में मदद कर सकती है।
यदि कुछ अक्ष (आमतौर पर समय अक्ष या किसी सरणी के सूचकांक) पर स्थित अंतराल का एक सेट है और आपको उनमें से कुछ को इष्टतम तरीके से चुनने की आवश्यकता है ताकि चयनित अंतराल प्रतिच्छेद न करें, तो आपको गतिशील प्रोग्रामिंग का उपयोग करने का प्रयास करना चाहिए
अनुमानित समाधान योजना:
प्रारंभ में, हम उपलब्ध अंतराल को सही सीमा के अनुसार क्रमबद्ध करते हैं। आइए निम्नलिखित गतिशीलता शुरू करें: dp[i] - पहले i अंतराल के लिए उत्तर।
हम निम्नानुसार पुनर्गणना करेंगे: पहले, इस स्थिति पर विचार करें कि इस अंतराल का उपयोग नहीं किया जाएगा, फिर बस dp[i] = dp[i-1]। ध्यान दें कि यह सुनिश्चित करता है कि जैसे-जैसे i बढ़ता है dp[i] का मान घटता नहीं है। और यह तार्किक है, क्योंकि। एक नया अंतर जोड़कर, हम वैश्विक उत्तर को खराब नहीं कर सकते: या तो हम नए अंतर को अनदेखा कर देते हैं, या हम इसका उपयोग करके एक अधिक लाभदायक संस्करण का निर्माण करते हैं। अब, यदि हम i-th गैप का उपयोग करना चाहते हैं, तो हम उन गैप्स का उपयोग कर सकते हैं, जिनकी दाहिनी सीमाएँ वर्तमान गैप की बाईं सीमा से कम हैं, क्योंकि हमें नॉन-ओवरलैपिंग गैप का एक सेट चुनना होगा। ऐसा करने के लिए, हमने शुरू में अंतराल को सही सीमा से क्रमबद्ध किया, ताकि अब हम आवश्यक स्थिति को कुशलतापूर्वक ढूंढ सकें। यदि संभव हो तो यह विश्लेषणात्मक रूप से किया जा सकता है, लेकिन सामान्य मामले में एक बिनसर्च के साथ एक अंतर खोजना संभव है, जिसकी दाहिनी सीमा वर्तमान की बाईं सीमा से कम है और साथ ही, अधिकतम संभव एक। हम लालची कारणों से सही सीमा को अधिकतम करना चाहते हैं, क्योंकि जैसे-जैसे मैं बढ़ता हूं, उत्तर केवल बढ़ सकता है। तदनुसार, हम आवश्यक स्थिति p पाते हैं और dp[i] को dp[p] और i-th अंतराल के माध्यम से पुनर्गणना करते हैं।