पायथन में सभी स्टॉप्स से गुजरने के लिए आवश्यक न्यूनतम बसों की संख्या खोजने का प्रोग्राम

मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है जो एक लाइन पर बस स्टॉप दिखाती है जहां nums[i] स्टेशन i पर बस के पहुंचने का समय दिखाता है। चूंकि बसें केवल आगे बढ़ सकती हैं, हमें सभी स्टॉप्स से गुजरने के लिए आवश्यक न्यूनतम बसों की संख्या ढूंढनी है।

उदाहरण के लिए, यदि इनपुट है nums = [1, 2, 7, 9, 3, 4], तो आउटपुट होगा 2, क्योंकि एक बस स्टॉप्स [1, 2, 3, 4] ले सकती है और दूसरी [7, 9] ले सकती है।

हल करने के चरण

• ans := 0
• seen := nums की लंबाई की सूची, प्रारंभ में false से भरी हुई।
• प्रत्येक इंडेक्स i और संबंधित n के लिए nums में:
  • यदि seen[i] गलत है, तो:
    • seen[i] := True
    • ans := ans + 1
    • prev := n
    • j को i+1 से nums के आकार तक:
      • यदि nums[j] > prev और seen[j] गलत है, तो:
        • seen[j] := True
        • prev := nums[j]
• ans लौटाएं।

उदाहरण

class Solution:
    def solve(self, nums):
        ans = 0
        seen = [False] * len(nums)
        for i, n in enumerate(nums):
            if not seen[i]:
                seen[i] = True
                ans += 1
                prev = n
                for j in range(i+1, len(nums)):
                    if nums[j] > prev and not seen[j]:
                        seen[j] = True
                        prev = nums[j]
        return ans

ob = Solution()
nums = [1, 2, 7, 9, 3, 4]
print(ob.solve(nums))

इनपुट

[1, 2, 7, 9, 3, 4]

आउटपुट

2