Glass annealer queue
MediumOnline Assessment
Work out when each piece comes out of a glass studio's shared annealing oven.
Freshly blown glass must be cooled slowly in an oven, one batch at a time. Each piece is [arrival, glass, thickness]: the minute it is placed in the waiting rack, its glass type, and its thickest wall in millimetres. A batch can only hold pieces of one glass type, because different glass shrinks at different rates. A piece thicker than 20 mm is always annealed alone. A batch of up to capacity pieces runs for 30 + 10 * t minutes, where t is the thickness of its thickest piece, and every piece in it comes out when the run ends.
Whenever the oven is idle (at minute 0, or the moment a run ends), and also whenever a piece arrives while it is idle, look at the waiting rack, which holds the pieces that have arrived (arrival <= now) and not yet been started. Take the oldest waiting piece (the earliest arrival; equal arrivals go in list order), and let G be its glass type. The oven starts a batch right now if any of these holds:
- the oldest piece is thicker than 20 mm;
- at least
capacitywaiting pieces of typeGare 20 mm or thinner; - the oldest piece has already waited
waitLimitminutes or more (now - arrival >= waitLimit).
The batch is then the oldest piece plus the earliest-arrived waiting pieces of type G that are 20 mm or thinner, up to capacity pieces in all (a thick oldest piece goes in alone). If none of the conditions holds, the oven stays idle and the question is asked again at the next arrival or when the oldest piece's wait reaches waitLimit, whichever comes first. A run that ends at minute f lets a new batch start at minute f.
Input: pieces, a list of [arrival, glass, thickness]; capacity and waitLimit, integers.
Output: a list with one integer per piece, in the order of pieces: the minute it comes out of the oven. Return [] for no pieces.
Example 1
- Input:
- [[[0,"soft",4],[2,"soft",6],[5,"boro",3],[8,"soft",5],[9,"boro",2]],3,20]
- Output:
- [98,98,158,98,158]
- Explanation
- With
capacity = 3andwaitLimit = 20, piece 0 (soft, 4 mm) is alone at minute 0 and the oven waits; the boro piece at 5 does not help it. At minute 8 a third soft piece is waiting, so a batch of pieces 0, 1 and 3 starts. Its thickest piece is 6 mm: it runs30 + 10 * 6 = 90minutes and ends at 98. The oldest waiting piece is now boro piece 2, which has waited 93 minutes, so the two boro pieces start together at 98 and run30 + 10 * 3 = 60, ending at 158.
Example 2
- Input:
- [[[0,"soft",25],[1,"soft",5],[2,"soft",21],[3,"soft",20],[4,"clear",8]],3,15]
- Output:
- [280,510,750,510,860]
- Explanation
- The 25 mm piece is thicker than 20 mm, so it starts alone at minute 0 and ends at
30 + 250 = 280. At 280 the oldest waiting piece is soft piece 1, which has waited 279 minutes, so a batch starts. A soft piece of exactly 20 mm counts as thin and joins it, but the 21 mm soft piece does not: the batch is pieces 1 and 3, runs30 + 200 = 230and ends at 510. The 21 mm piece is now the oldest and runs alone until 750, then theclearpiece runs until 860.
Example 3
- Input:
- [[[0,"clear",2],[12,"soft",3],[15,"soft",4]],2,10]
- Output:
- [60,130,130]
- Explanation
- The lone
clearpiece (2 mm) waits until minute 10, whenwaitLimitis reached, and runs alone: it ends at10 + 30 + 20 = 60. The two soft pieces form a full batch ofcapacity = 2as soon as the second arrives at 15, but the oven is busy until 60, so the batch starts at 60, runs30 + 40 = 70and ends at 130.
Constraints
0 <= pieces.length <= 4000 <= arrival <= 100,000;1 <= thickness <= 60; glass types are lowercase strings1 <= capacity <= 10;0 <= waitLimit <= 5,000