Chương trình tìm số bus tối thiểu để đi qua tất cả các trạm trong Python

Cho danh sách nums thể hiện các trạm xe buýt trên một tuyến, nums[i] là thời gian xe buýt phải đến trạm i. Xe buýt chỉ đi tiến về phía trước. Tìm số lượng xe buýt tối thiểu để đi qua tất cả các trạm.

Ví dụ, nums = [1, 2, 7, 9, 3, 4], đầu ra là 2, vì một xe có thể lấy các trạm [1, 2, 3, 4] và xe khác lấy [7, 9].

Các bước giải quyết:

• ans := 0.
• seen := danh sách độ dài bằng nums khởi tạo False.
• Duyệt từng chỉ số i và giá trị n trong nums:
  • Nếu seen[i] là False:
    • seen[i] = True.
    • ans += 1.
    • prev = n.
    • Với j từ i+1 đến cuối:
      • Nếu nums[j] > prev và seen[j] là False:
        • seen[j] = True.
        • prev = nums[j].
• Trả về ans.

Ví dụ minh họa

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))

Đầu vào

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

Đầu ra

2