कोडिंग इंटरव्यू: गैर-अतिव्यापी (non-overlapping) जॉब्स के साथ रिवॉर्ड को अधिकतम कैसे करें?

प्रॉम्प्ट और उपयोग के मामले

प्रत्येक जॉब (start, end, reward) है। अधिकतम कुल रिवॉर्ड वाले संगत जॉब्स चुनें; समाप्ति समय अगली शुरुआत के बराबर होने की अनुमति है। (1,3,50), (3,5,40), (2,6,100) के लिए, पहले दो जॉब्स रिवॉर्ड 90 के साथ जीतते हैं। यह एक coding प्रश्न है जो कार्यान्वयन भाषा की परवाह किए बिना इंटरवल ऑर्डरिंग, पूर्ववर्ती लुकअप (predecessor lookup) और डायनामिक प्रोग्रामिंग का परीक्षण करता है।

सार्वजनिक एल्गोरिदम सामग्री वेटेड इंटरवल/जॉब शेड्यूलिंग का उपयोग एक डायनामिक-प्रोग्रामिंग और इंटरवल-पैटर्न अभ्यास के रूप में करती है, और एक सार्वजनिक इंटरव्यू विवरण भी एक इंटरवल-शेड्यूलिंग संस्करण को रिकॉर्ड करता है। इंटरव्यू की अप्रमाणित आवृत्ति का दावा किए बिना सत्यापन योग्य आवश्यकताएं बताएं।

इंटरव्यूअर क्या मूल्यांकन करता है

• क्या आप समाप्ति समय के अनुसार सॉर्ट करते हैं ताकि अंतिम चुना गया जॉब एक क्रमित निर्णय बना सके।
• क्या आप p(i) को परिभाषित करते हैं, जो जॉब i के शुरू होने से पहले समाप्त होने वाला अंतिम जॉब है।
• क्या आप केवल सबसे बड़े व्यक्तिगत रिवॉर्ड को लालच से (greedily) लेने के बजाय वर्तमान जॉब को छोड़ने और लेने की तुलना करते हैं।
• क्या बाइनरी सर्च पूर्ववर्ती लुकअप को O(log n) तक कम कर देता है और क्या आप चुने गए जॉब्स को फिर से बना (reconstruct) सकते हैं।
• क्या आप end == start, समान समाप्ति समय, खाली इनपुट और शून्य रिवॉर्ड को संभालते हैं।

उत्तर देने से पहले स्पष्टीकरण

• क्या समान समाप्ति और शुरुआत का समय संगत है? यह उत्तर हाँ मानता है: end <= start।
• क्या रिवॉर्ड नकारात्मक हो सकते हैं? यदि हां, तो आधारभूत 0 के साथ स्पष्ट रूप से कोई जॉब न चुनने की अनुमति दें।
• क्या केवल अधिकतम रिवॉर्ड की आवश्यकता है? यह लेख जॉब सेट का भी पुनर्निर्माण करता है; यदि आवश्यक न हो तो पैरेंट डेटा छोड़ दें।
• क्या समय पूर्णांक हैं? सॉर्टिंग के लिए केवल तुलनीयता की आवश्यकता होती है; बाइनरी सर्च को क्रमिक पूर्णांकों की आवश्यकता नहीं होती है।
• क्या किसी जॉब को दो बार चुना जा सकता है? मान लें कि प्रत्येक इनपुट जॉब को अधिकतम एक बार चुना जा सकता है।
• क्या start > end हो सकता है? पुनरावृत्ति (recurrence) से पहले इसे अस्वीकार या सामान्य करें; अमान्य डेटा न छिपाएं।
• समान अंतरालों को कैसे व्यवस्थित किया जाना चाहिए? एक स्थिर टाई-ब्रेक का उपयोग करें; कोई भी इष्टतम रिवॉर्ड स्वीकार्य है।

30-सेकंड उत्तर ढांचा

"मैं जॉब्स को end द्वारा सॉर्ट करता हूं और dp[i] को पहले i जॉब्स से सर्वोत्तम रिवॉर्ड मानता हूं। जॉब i के लिए, बाइनरी सर्च से अंतिम जॉब खोजें जिसका अंत अधिकतम start[i] हो; इसके संगत उपसर्ग आकार (prefix size) को p कहें। पुनरावृत्ति dp[i] = max(dp[i-1], reward[i] + dp[p]) है: जॉब को छोड़ें या इसे इसके संगत उपसर्ग के साथ लें। मैं एक विकल्प मार्कर संग्रहीत करता हूं और जॉब्स को पुनर्प्राप्त करने के लिए बैकट्रैक करता हूं। सॉर्टिंग और प्रत्येक बाइनरी सर्च O(n log n) समय देते हैं और ऐरे O(n) स्पेस का उपयोग करते हैं।"

चरण-दर-चरण गहन उत्तर

चरण 1: समझाएं कि लालची (greedy) नियम अपर्याप्त क्यों है।

जल्दी समाप्त होने वाला समय (Earliest-finish-time) लालची दृष्टिकोण तब सही होता है जब प्रत्येक जॉब का मूल्य समान होता है। अलग-अलग रिवॉर्ड के साथ, एक छोटा कम-मूल्य वाला जॉब बेहतर संयोजन को रोक सकता है, इसलिए स्थानीय समाप्ति समय या स्थानीय रिवॉर्ड पर्याप्त नहीं है।

चरण 2: क्रमित स्थिति (ordered state) को परिभाषित करें।

सॉर्ट करने के बाद, मान लें कि dp[i] जॉब्स 0..i-1 के लिए इष्टतम है, जहां dp[0] = 0 है। जॉब i-1 को छोड़ने पर तुरंत dp[i-1] मिलता है।

चरण 3: पूर्ववर्ती (predecessor) की गणना करें।

जॉब i-1 के लिए, end[j] <= start[i-1] के साथ सबसे बड़ा j < i-1 खोजें। सॉर्ट किए गए समाप्ति समय पर बाइनरी सर्च करें और इसका संगत उपसर्ग आकार p लौटाएं; जॉब लेने पर reward[i-1] + dp[p] प्राप्त होता है।

चरण 4: पुनरावृत्ति और पुनर्निर्माण लिखें।

dp[0] = 0
for i = 1..n:
  skip = dp[i - 1]
  take = reward[i - 1] + dp[p(i - 1)]
  dp[i] = max(skip, take)
  chose[i] = take > skip

i = n से बैकट्रैक करें: यदि chose[i] सत्य है, तो जॉब i-1 रिकॉर्ड करें और p(i-1) पर जाएं; अन्यथा i घटाएं। एकत्रित सूची को उलट दें। जब दो रिवॉर्ड समान हों तो एक टाई-ब्रेक तय करें।

चरण 5: शुद्धता सिद्ध करें।

पहले i जॉब्स पर कोई भी इष्टतम या तो जॉब i-1 को बाहर करता है, जिससे अधिकतम dp[i-1] प्राप्त होता है, या इसे शामिल करता है। बाद के मामले में हर दूसरा जॉब पहले p(i-1) संगत जॉब्स में आता है, जिससे अधिकतम reward[i-1] + dp[p(i-1)] प्राप्त होता है। पुनरावृत्ति इन संपूर्ण मामलों में से बड़े को लेती है। बेस केस dp[0] = 0 के साथ, गणितीय आगमन (induction) प्रत्येक स्थिति को इष्टतम सिद्ध करता है।

चरण 6: कार्यान्वयन सीमाओं की रक्षा करें।

पूर्ववर्ती खोज में <= का उपयोग होना चाहिए ताकि आसन्न जॉब्स संगत बने रहें। नकारात्मक रिवॉर्ड और खाली सेट का समर्थन करने के लिए शून्य से प्रारंभ करें। बैकट्रैकिंग परिणाम को उलट दें क्योंकि पुनर्निर्माण अंत से चलता है।

चरण 7: जटिलता का विश्लेषण करें।

सॉर्टिंग की लागत O(n log n) है, और प्रति जॉब एक बाइनरी सर्च की लागत भी कुल मिलाकर O(n log n) है। डायनामिक-प्रोग्रामिंग, पूर्ववर्ती और विकल्प ऐरे O(n) स्पेस का उपयोग करते हैं। यदि आउटपुट आकार गिना जाता है तो उसे अलग से बताएं।

चरण 8: विकल्पों की पहचान करें।

यदि समाप्ति समय छोटे परिबद्ध पूर्णांक (bounded integers) हैं, तो एक समय-अनुक्रमित स्कैन तुलना सॉर्टिंग से बच सकता है। यदि रिवॉर्ड समान हैं, तो जल्द से जल्द समाप्त होने वाला लालची दृष्टिकोण पर्याप्त है। अधिकतम k जॉब्स या एकाधिक संसाधनों की सीमा स्थिति आयाम जोड़ती है और एक नई पुनरावृत्ति की आवश्यकता होती है।

उच्च गुणवत्ता वाला नमूना उत्तर

"मैं समाप्ति समय के अनुसार सॉर्ट करता हूं और dp[i] को पहले i जॉब्स के बीच अधिकतम रिवॉर्ड के रूप में परिभाषित करता हूं। प्रत्येक जॉब के लिए, end <= start के साथ अंतिम पूर्ववर्ती को बाइनरी सर्च करें। छोड़ने पर dp[i-1] मिलता है; लेने पर reward[i] + dp[p(i)] मिलता है, इसलिए मैं बड़ा मान रखता हूं और बैकट्रैकिंग के लिए विकल्प रिकॉर्ड करता हूं। प्रमाण प्रत्येक इष्टतम को इस आधार पर विभाजित करता है कि क्या इसमें वर्तमान जॉब शामिल है; यदि ऐसा है, तो शेष जॉब्स संगत उपसर्ग से आने चाहिए। सॉर्टिंग और बाइनरी सर्च O(n log n) समय और O(n) सहायक स्थान देते हैं। मैं आसन्न जॉब्स, समान समाप्ति समय, नकारात्मक रिवॉर्ड, पूर्ण ओवरलैप और खाली इनपुट का परीक्षण करता हूं।"

सामान्य गलतियाँ

• सबसे बड़े रिवॉर्ड द्वारा लालची दृष्टिकोण → एक जॉब उच्च-योग वाले संयोजन को अवरुद्ध कर सकता है → DP के साथ लेने और छोड़ने की तुलना करें।
• समान अंत/शुरुआत को टकराव मानना → वैध आसन्न जॉब्स गायब हो जाते हैं → end <= start का उपयोग करें।
• केवल शुरुआत के आधार पर सॉर्ट करना → dp[i-1] अब एक स्थिर उपसर्ग का वर्णन नहीं करता है → अंत के आधार पर सॉर्ट करें।
• रैखिक पूर्ववर्ती स्कैन → कुल समय O(n²) हो जाता है → समाप्ति समय पर बाइनरी सर्च करें।
• पहले रिवॉर्ड से प्रारंभ करना → सभी-नकारात्मक इनपुट खाली सेट नहीं चुन सकते → dp[0] = 0 सेट करें।
• बैकट्रैकिंग को उलटना भूल जाना → चयनित जॉब्स उल्टे लौटाए जाते हैं → संग्रह के बाद उलटें।
• समान-रिवॉर्ड वाले टाई को अनिर्दिष्ट छोड़ना → विभिन्न रन में आउटपुट बदल जाता है → एक टाई-ब्रेक तय करें।
• यह दावा करना कि एक आयाम संसाधन सीमाओं को संभालता है → अतिरिक्त बाधाओं का प्रतिनिधित्व नहीं किया गया है → आयाम जोड़ें या फिर से मॉडल बनाएं।

अनुवर्ती प्रश्न और उत्तर

अनुवर्ती 1: समान-सीमा नियम सुरक्षित क्यों है?

यदि कोई जॉब ठीक उसी समय समाप्त होता है जब दूसरा शुरू होता है, तो वे उल्लिखित परिपाटी के तहत ओवरलैप नहीं करते हैं। इसलिए पूर्ववर्ती परीक्षण में समानता शामिल होनी चाहिए; इसे < में बदलना एक अलग समस्या को हल करता है।

अनुवर्ती 2: क्या यह हमेशा O(n) हो सकता है?

छोटे परिबद्ध पूर्णांक समय के साथ, प्रत्यक्ष समय स्कैनिंग रैखिक हो सकती है। सामान्य तुलना मॉडल में, सॉर्टिंग की लागत ही O(n log n) होती है, इसलिए बिना शर्त रैखिक समय का वादा न करें।

अनुवर्ती 3: आप जॉब्स का पुनर्निर्माण कैसे करते हैं?

एक विकल्प बिट या पैरेंट पॉइंटर संग्रहीत करें। i = n से, वर्तमान जॉब लें और इसके पूर्ववर्ती पर जाएं, या छोड़ते समय घटाएं; एकत्रित जॉब्स को उलट दें।

अनुवर्ती 4: क्या होगा यदि अधिकतम k जॉब्स का चयन किया जा सकता है?

पहले i में से c जॉब्स का उपयोग करके सर्वोत्तम रिवॉर्ड के लिए dp[i][c] जैसा एक गणना आयाम जोड़ें। समय और स्थान तदनुसार बढ़ जाते हैं।

अनुवर्ती 5: क्या होगा यदि रिवॉर्ड आसन्न जॉब्स पर निर्भर करता है?

स्वतंत्र-रिवॉर्ड की धारणा अब मान्य नहीं है। स्थिति में आसन्नता शामिल करें या इसे संक्रमण लागत के रूप में मॉडल करें; उस परिवर्तन के बिना मूल पुनरावृत्ति उचित नहीं है।

अनुवर्ती 6: क्या होगा यदि सभी जॉब्स का समाप्ति समय समान हो?

स्थिर सॉर्टिंग पर्याप्त है। उनके पूर्ववर्ती आमतौर पर समान होते हैं, और पुनरावृत्ति अभी भी प्रत्येक उम्मीदवार की तुलना करती है। समान अंतरालों के लिए, केवल सर्वोत्तम रिवॉर्ड मायने रखता है।

अनुवर्ती 7: लालची दृष्टिकोण कब सही होता है?

जब सभी रिवॉर्ड समान हों और लक्ष्य अधिकतम संख्या में जॉब्स का चयन करना हो, तो जल्द से जल्द समाप्त होने वाले लालची दृष्टिकोण में एक एक्सचेंज तर्क (exchange argument) होता है। असमान रिवॉर्ड के साथ, भारित डायनामिक प्रोग्रामिंग का उपयोग करें।