FastPrep
Problem · Array

Minimum Cost to Attend Required Courses

Learn this problem
● MediumVisaFULLTIMEOA

Problem statement

You must attend courses on the days listed in courseDays, which is sorted in strictly increasing order. You may buy any of the reusable pass options described by the parallel arrays passDurations and passCosts.

If you buy option j on day d, it costs passCosts[j] and covers every required course day from d through d + passDurations[j] - 1, inclusive. You may buy an option on the first required course day that is not already covered.

Return the minimum total cost needed to cover every required course day. If courseDays is empty, return 0.

Function

minimumCourseCost(courseDays: int[], passDurations: int[], passCosts: int[]) → int

Examples

Example 1

courseDays = [1,4,6,7,8,20]passDurations = [1,7,30]passCosts = [2,7,15]return = 11

Buy one-day passes for days 1 and 20, and a seven-day pass on day 4 to cover days 4, 6, 7, and 8. The total cost is 2 + 7 + 2 = 11.

Example 2

courseDays = [1,2,3,4,5,6,7,8]passDurations = [1,3,8]passCosts = [3,6,14]return = 14

An eight-day pass bought on day 1 covers every required day for cost 14, which is cheaper than combining shorter passes.

Example 3

courseDays = []passDurations = [1,7]passCosts = [4,18]return = 0

No course days require coverage, so no pass is purchased.

Constraints

  • 0 <= courseDays.length <= 100000
  • courseDays contains distinct positive integers in strictly increasing order.
  • 1 <= passDurations.length = passCosts.length <= 100
  • 1 <= passDurations[i] <= 1000000000
  • 1 <= passCosts[i] <= 1000000
  • The minimum total cost fits in a signed 32-bit integer.

More Visa problems

drafts saved locally
public int minimumCourseCost(int[] courseDays, int[] passDurations, int[] passCosts) {
    // write your code here
}
courseDays[1,4,6,7,8,20]
passDurations[1,7,30]
passCosts[2,7,15]
expected11
checking account