Program to find minimum number of busses are required to pass through all stops in Python

Question

Program to find minimum number of busses are required to pass through all stops in Python

PythonServer Side ProgrammingProgramming

---

---

Suppose we have a list of numbers called nums and that is showing the bus stops on a line where nums[i] shows the time a bus must arrive at station i. Now that buses can only move forward, we have to find the minimum number of buses that are needed to pass through all the stops.

So, if the input is like nums = [1, 2, 7, 9, 3, 4], then the output will be 2, as one bus can take stops [1, 2, 3, 4] and another can do [7, 9].

To solve this, we will follow these steps−

• ans := 0

• seen := a list whose length is same as nums and initially filled with false

• for each index i and corresponding n in nums, do

  • if seen[i] is false, then

    • seen[i] := True

    • ans := ans + 1

    • prev := n

    • for j in range i+1 to size of nums, do

      • if nums[j] > prev and seen[j] is false, then

        • seen[j] := True

        • prev := nums[j]

• return ans

Let us see the following implementation to get better understanding −

Example

Live Demo

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

Input

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

Output

2

Arnab Chakraborty

Published on 05-Oct-2020 16:02:17

Previous Page Print Page

Next Page  

Advertisements