Problem statement

https://binarysearch.com/problems/Bus-Fare/

Solution

Equal to Leetcode 0983. Minimum Cost For Tickets.

Complexity

It is O(n), where n = len(days).

Code

class Solution:
    def solve(self, days):
        k, P, cost, costs = 3, [1,7,30], 0, [2, 7, 25]
        Q = [deque() for _ in range(k)]

        for d in days:
            for i in range(k):
                while Q[i] and Q[i][0][0] + P[i] <= d: Q[i].popleft()
                Q[i].append([d, cost + costs[i]])
         
            cost = min([Q[i][0][1] for i in range(k)])

        return cost