Run many tasks with at most K at a time, the way a server limits how many requests it sends at once.
What to build
A program that simulates a pool of K workers running timed tasks.
Requirements
- Declare
interface Job { name: string; ms: number }and run the jobs with K async workers that share one queue, taking jobs in input order. - When a worker starts a job print
start NAME at T; when it finishes printdone NAME at T, where T is the simulated time in milliseconds (the run starts at 0). A worker that finishes a job prints its done line and then starts its next job at the same time. - At the end print
total T, the time the last job finished.
Input
Line 1: K and n. Then n lines NAME MS.
Output
2n lines, then the total.
Constraints
1 ≤ K ≤ 5; 1 ≤ n ≤ 20; 1 ≤ MS ≤ 10000; no two jobs finish at the same time.
Example
Input:
2 4
a 300
b 100
c 250
d 60
Output:
start a at 0
start b at 0
done b at 100
start c at 100
done a at 300
start d at 300
done c at 350
done d at 360
total 360
Why it works
Each worker awaits one job at a time, so at most K timers are pending, and because a worker takes the next job as soon as it is free, the pool finishes far sooner than one worker would while never running more than K at once.
Examples
2 4 a 300 b 100 c 250 d 60
start a at 0 start b at 0 done b at 100 start c at 100 done a at 300 start d at 300 done c at 350 done d at 360 total 360
1 2 x 10 y 20
start x at 0 done x at 10 start y at 10 done y at 30 total 30
Hints
Hint 1
Start K async workers; each takes the next task from a shared queue until it is empty.
Hint 2
Time is simulated: a task that starts at time S with duration D finishes at S + D, so keep the clock in a variable you update when a task finishes.
Solution
Show one correct solution (try it yourself first)
const read = (): string => prompt() ?? "";
interface Job {
name: string;
ms: number;
}
function wait(ms: number): Promise<void> {
return new Promise((resolve) => setTimeout(resolve, ms));
}
const [k, n] = read().split(" ").map(Number);
const queue: Job[] = [];
for (let i = 0; i < n; i++) {
const [name, ms] = read().split(" ");
queue.push({ name, ms: Number(ms) });
}
let clock = 0;
async function worker(): Promise<void> {
for (let job = queue.shift(); job; job = queue.shift()) {
const start = clock;
console.log("start " + job.name + " at " + start);
await wait(job.ms);
clock = start + job.ms;
console.log("done " + job.name + " at " + clock);
}
}
async function main(): Promise<void> {
const workers: Promise<void>[] = [];
for (let i = 0; i < k; i++) workers.push(worker());
await Promise.all(workers);
console.log("total " + clock);
}
main();