739. Travel Pass Planner
A commuter plans to ride the tram on certain days of the year. The list days holds the day numbers on which a ride is needed; it may be in any order and may repeat a day, and a repeated day still needs only one pass. The tram sells three kinds of passes and costs lists their prices: costs[0] for a 1-day pass, costs[1] for a 7-day pass and costs[2] for a 30-day pass. A pass bought for day d covers days d to d+len-1 and passes may be bought in any combination.
Return the lowest total price that covers every day in days. Prices are not guaranteed to grow with duration. Aim for time O(n log n) and space O(n).
Example 1
- Input:
- days = [4,5,9,10,11,40], costs = [3,10,20]
- Output:
- 16
- Explanation:
A 7-day pass from day 4 covers days 4, 5, 9 and 10 for 10, then days 11 and 40 take a 1-day pass each at 3, total 16.
Example 2
- Input:
- days = [2,3,4,5,6,7,8], costs = [6,10,50]
- Output:
- 10
- Explanation:
One 7-day pass starting on day 2 covers all seven days for 10, far below buying seven 1-day passes.
Example 3
- Input:
- days = [10,60,110], costs = [2,15,40]
- Output:
- 6
- Explanation:
The days are far apart, so three 1-day passes at 2 each cost 6.
Constraints
1 ≤ days.length ≤ 6 * 104
1 ≤ days[i] ≤ 109
costs.length = 3, 1 ≤ costs[i] ≤ 1000
The answer fits in a 32-bit signed integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)