पायथन में अंतराल समय के आधार पर अधिकतम कोर्स लेने का प्रोग्राम

कोर्स के अंतराल [start, end] की एक सूची दी गई है। हम एक समय में केवल एक कोर्स ले सकते हैं, और अगला कोर्स पिछले कोर्स के अंत समय के बाद शुरू होना चाहिए। अधिकतम कितने कोर्स लिए जा सकते हैं?

उदाहरण

इनपुट: times = [[3, 6], [6, 9], [7, 8], [9, 11]]

आउटपुट: 3

चुने गए कोर्स: [3, 6], [7, 8], [9, 11]

एल्गोरिदम (लालची दृष्टिकोण)

1. कोर्स को उनके अंत समय (end) के आधार पर आरोही क्रम में सॉर्ट करें।
2. counter = 0 और end = -1 प्रारंभ करें।
3. प्रत्येक कोर्स [s, e] के लिए:
   • यदि s > end (सख्ती से बाद में शुरू होता है), तो:
     • counter += 1
     • end = e
4. counter वापस करें।

पायथन कार्यान्वयन

class Solution:
    def solve(self, times):
        # अंत समय के अनुसार सॉर्ट करें
        times.sort(key=lambda x: x[1])
        counter = 0
        end = -1
        for s, e in times:
            if s > end:
                counter += 1
                end = e
        return counter

# परीक्षण
ob = Solution()
times = [[3, 6], [6, 9], [7, 8], [9, 11]]
print(ob.solve(times))  # आउटपुट: 3

क्यों काम करता है?

सबसे पहले खत्म होने वाले कोर्स को चुनने से भविष्य के कोर्स के लिए अधिकतम समय बचता है। यह क्लासिक "इंटरवल शेड्यूलिंग" समस्या का लालची समाधान है।

समय जटिलता

• सॉर्टिंग के कारण O(n log n)।
• स्थान जटिलता: O(1) अतिरिक्त (इन-प्लेस सॉर्ट मानकर)।

नोट

यदि कोर्स के शुरू और अंत समय समान हो सकते हैं (जैसे [3,6] और [6,9]), तो शर्त s >= end का उपयोग करें। यहां s > end उपयोग किया गया है जैसा कि समस्या विवरण में "बाद में" कहा गया है।