FastPrep
Problem · Dynamic Programming

Minimum Preparation Time for Two Handlers

Learn this problem
● MediumAmazon logoAmazonFULLTIMEOA
See Amazon hiring insights

Problem statement

A work queue workList must be processed in order by two handlers. Each value in workList is a work type from 1 through m.

For work type t, the first time a handler processes that type, or whenever the handler's previous job was a different type, that handler pays longPrepTime[t]. If the handler's previous job was the same type, that handler pays shortPrepTime[t] instead.

Each job must be assigned to exactly one of the two handlers, and jobs must be processed in the order they appear. Return the minimum total preparation time.

Function

minPreparationTime(workList: int[], longPrepTime: int[], shortPrepTime: int[]) → int

Complete the function minPreparationTime in the editor below.

minPreparationTime has the following parameters:

  1. int[] workList: the ordered work types
  2. int[] longPrepTime: long preparation time for each work type
  3. int[] shortPrepTime: short preparation time for each work type

Returns

int: the minimum total preparation time.

Examples

Example 1

workList = [1, 2, 2]longPrepTime = [4, 5]shortPrepTime = [2, 3]return = 12

Assign work type 1 to the first handler, then assign both type-2 jobs to the second handler. The total cost is 4 + 5 + 3 = 12.

Example 2

workList = [1, 1, 1]longPrepTime = [4]shortPrepTime = [2]return = 8

Use the same handler for all three jobs to pay one long preparation and two short preparations.

Constraints

  • workList[i] identifies a work type between 1 and m
  • longPrepTime and shortPrepTime contain one entry per work type.
  • Jobs must be processed in order.

More Amazon problems

drafts saved locally
public int minPreparationTime(int[] workList, int[] longPrepTime, int[] shortPrepTime) {
    // write your code here
}
workList[1, 2, 2]
longPrepTime[4, 5]
shortPrepTime[2, 3]
expected12
checking account