We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Cost For Tickets

Number: 1025

Difficulty: Medium

Paid? No

Companies: Meta, Turing, Amazon, Uber, TikTok, Google, Adobe, Flipkart, PhonePe, Grab

Problem Description

Given a sorted list of days on which you will travel and the cost of three different types of train tickets (1-day, 7-day, and 30-day passes), determine the minimum amount of money required to cover all travel days. Each ticket covers a consecutive range of days—using it on a specified day covers a fixed number of days into the future.

Key Insights

  • Use dynamic programming to build up a solution using the minimum cost required up to each day.
  • For each travel day, consider purchasing a 1-day, 7-day, or 30-day pass and choose the one that minimizes the total cost.
  • Skip days without travel since they do not affect the overall cost.
  • Use a DP array keyed by day or simulate the process using pointers with the travel days list.

Space and Time Complexity

Time Complexity: O(n + last_day) where n is the number of travel days and last_day is the maximum day value. In practice, O(365) due to the year constraint. Space Complexity: O(last_day) which is O(365) in the worst-case scenario.

Solution

The solution uses dynamic programming. We maintain a DP array (or dictionary) where dp[d] represents the minimum cost to cover all travel days up to day d. For each day d from 1 to the last travel day:

  • If d is not a travel day, then dp[d] = dp[d-1] because no additional cost is incurred.
  • If d is a travel day, then we calculate:
    • The cost if a 1-day pass is purchased today: dp[d-1] + costs[0].
    • The cost if a 7-day pass is used: dp[max(0, d-7)] + costs[1].
    • The cost if a 30-day pass is used: dp[max(0, d-30)] + costs[2].
  • We then set dp[d] as the minimum of these three computed values.

This DP approach ensures that we account for the overlapping intervals provided by the different passes and choose the optimal cost at each travel day.

Code Solutions

# Python solution with detailed comments
def mincostTickets(days, costs):
    # Create an array dp with size up to the last travel day + 1
    last_day = days[-1]
    dp = [0] * (last_day + 1)
    travel_days = set(days)  # Using a set for O(1) look-up

    for day in range(1, last_day + 1):
        if day not in travel_days:
            # If it's not a travel day, cost remains as previous day's cost
            dp[day] = dp[day - 1]
        else:
            # Calculate cost if we buy a 1-day, 7-day, or 30-day pass
            cost1 = dp[day - 1] + costs[0]
            cost7 = dp[max(0, day - 7)] + costs[1]
            cost30 = dp[max(0, day - 30)] + costs[2]
            # Choose the minimum cost option
            dp[day] = min(cost1, cost7, cost30)
    return dp[last_day]

# Example usage:
print(mincostTickets([1,4,6,7,8,20], [2,7,15]))
← Back to All Questions