You are given a sequence of jobs that must be processed in the given order. There are exactly two handlers, and each job must be assigned to one of them.
Each job has a type. Let workList[i] be the type of the i-th job. For each job type t, you are also given:
-
longPrepTime[t]
: the cost for a handler to process type
t
if this is the first job that handler has ever processed, or if the handler's most recent job type is different from
t
-
shortPrepTime[t]
: the cost for a handler to process type
t
if the handler's most recent job type is also
t
Initially, both handlers have processed nothing.
Your task is to assign every job in workList to one of the two handlers so that the total preparation time is minimized.
Example:
-
workList = [1, 2, 2]
-
longPrepTime = [4, 5]
-
shortPrepTime = [2, 3]
Assume job types are 1-indexed, so:
-
type
1
has
longPrepTime = 4
,
shortPrepTime = 2
-
type
2
has
longPrepTime = 5
,
shortPrepTime = 3
One optimal assignment is:
-
handler A processes job type
1
with cost
4
-
handler B processes job type
2
with cost
5
-
handler B processes job type
2
again with cost
3
So the minimum total time is 12.
Return the minimum total preparation time.