Skip to content
Katabench
Try free

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

C#
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.

C# coding challenges →

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