Problem 597946 · hard · Phase 05 Advanced Algorithms & Graphs

Pottery Kiln Queue

gauntlet · simulation · scheduling · priority

A pottery studio has one kiln. Firing jobs are given as jobs, a list of [name, arrival, length, level]: the job becomes available at moment arrival and needs length units of kiln time in total. level is its urgency class: a smaller level is more urgent. Levels always stay between 1 and 9. You are also given quantum and age.

Time is measured in whole units; unit T runs from moment T to moment T + 1. The waiting line is ordered by the moment each job last joined it, and within the same moment by the order in which the rules below add them. At every moment T = 0, 1, 2, ... apply these steps in order:

  1. Finish. If the job in the kiln has received all of its length, it leaves and is recorded as [name, T]. The kiln is empty.
  2. Arrive. Jobs with arrival == T join the waiting line, in the order they appear in jobs.
  3. Quantum. If a job is still in the kiln and has run quantum units since it was last put in, its level goes up by one (at most 9) and it rejoins the waiting line. The kiln is empty.
  4. Pre-empt. If a job is still in the kiln and some waiting job has a strictly smaller level, the job in the kiln rejoins the waiting line with its level unchanged. The kiln is empty.
  5. Load. If the kiln is empty and the line is not, take out the waiting job with the smallest level; among equal levels, the one earliest in the line. (It may be the job that just left.)
  6. Fire. If a job is in the kiln, it runs during unit T. Then every job still waiting has waited one more unit; a job that has now waited age units since it last joined the line or was last promoted is promoted: its level goes down by one (at least 1) and its count starts again from zero. Promotion does not change a job's place in the line.

Return the list of [name, finish_moment] in the order the jobs finish.

Examples

Input:  jobs = [["A",0,5,2], ["B",1,3,1]], quantum = 2, age = 10
Output: [["B",6], ["A",8]]

Input:  jobs = [["X",0,6,3], ["Y",0,2,3], ["Z",2,3,1]], quantum = 3, age = 2
Output: [["Z",5], ["Y",7], ["X",11]]

Constraints

  • 1 <= len(jobs) <= 200, names are distinct
  • 0 <= arrival <= 1000, 1 <= length <= 50, 1 <= level <= 9
  • 1 <= quantum <= 50, 1 <= age <= 100

Goals

  • Implement a scheduler whose rules must run in an exact order at every moment
  • Keep a stable waiting order that promotions do not disturb
  • Handle rules that fire at the same moment without letting one hide another
Starting Python…