All problems

Print Shop Schedule

Medium · heap

A print shop has a list of jobs. jobs[i] is the type of the i-th job (a non-negative number such as a paper or ink kind). The shop prints exactly one job in every minute, and it can print the jobs in any order.

After a job of some type is printed, the machine must rest from that type for cooldown whole minutes: the next job of the same type cannot be printed until cooldown minutes have passed. Jobs of other types are not affected. If cooldown is 0, the same type can be printed again in the very next minute.

The shop follows one fixed rule. In every minute it looks at the types that are ready (not resting) and still have unprinted jobs, and prints one job of the type with the most unprinted jobs. If several ready types have the same number of unprinted jobs, it prints the one with the smallest type number. If no type is ready but some jobs remain, the minute is idle.

Return a list with one entry per minute, from the first minute until the last job is printed: the type that was printed, or -1 for an idle minute.

Examples

Example 1

Input: jobs = [1, 1, 2, 2, 2, 3], cooldown = 1

Output: [2, 1, 2, 1, 2, 3]

Type 2 has the most jobs, so it goes first and rests for a minute. Type 1 goes next, then type 2 again, which is ready and still has more jobs left than type 3. Type 1 and type 3 now tie, so the smaller type 1 goes, then type 2, which is ready again and smaller than 3. Type 3 goes last.

Example 2

Input: jobs = [5, 5, 5], cooldown = 2

Output: [5, -1, -1, 5, -1, -1, 5]

Only one type exists, so after each print the shop waits two idle minutes.

Example 3

Input: jobs = [4, 7, 4], cooldown = 0

Output: [4, 4, 7]

With no rest, type 4 (two jobs) goes first. Then 4 and 7 have one job each, and the tie goes to the smaller type, 4.

Constraints