Minimum Travel Pass Cost
Medium About 25 min Free, no account needed
Cover sparse travel dates with overlapping pass durations while paying for no unnecessary calendar state.
The brief
days contains strictly increasing travel dates. Pass option p costs costs[p] and covers durations[p] consecutive days, including the purchase date. Buy any number of passes. Return the minimum total cost covering every travel date.
For days = [1, 2, 8, 9], durations = [1, 7], costs = [3, 5], the answer is 10: buy a seven-day pass on day 1 and another on day 8. The first pass expires before day 8.
The arrays durations and costs have equal lengths from 1 to 8; their values are positive 32-bit integers. Pass options need not be ordered or cost-effective. Dates are positive 32-bit integers, with up to 100,000 travel dates. Empty travel costs 0. Return a 64-bit total and leave all inputs unchanged. Iterating across the entire calendar is unsafe for widely separated dates.
Starter code
using System;
public class Solution
{
public long Solve(int[] days, int[] durations, int[] costs)
{
// TODO: implement the contract without changing the input.
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Dynamic programming
- Define subproblems and a recurrence, then reuse solved subproblems instead of recomputing them.
- Binary search
- Halve a sorted search space, with exact boundaries and no off-by-one drift.
Related katas
- Longest Increasing Subsequence Medium Free Length of the longest strictly increasing subsequence - faster than the quadratic DP.
- Weighted Reservation Schedule Hard Free Choose a maximum-value set of nonoverlapping reservations with a mandatory cleanup gap.
- Coin Change (Fewest Coins) Medium Free The fewest coins that make the amount, or -1.
- Coin Change II (Count the Ways) Medium Free How many coin combinations make the amount?