Schedule tasks with a concurrency limit — interview question

A common interview task is runWithLimit(tasks, k): run asynchronous tasks so that at most k are in progress at once, starting them in list order and starting the next one the moment any running task finishes (like p-limit or a hand-written promise pool).

You are given the duration of each task. Simulate the pool from time 0 and print when every task finishes.

At time 0, the first min(k, n) tasks start.
Whenever tasks finish at time t, the same number of waiting tasks (in list order) start at time t.
Print one line per task, <task number> <finish time>, sorted by finish time; when several tasks finish at the same time, print them in task-number order. Tasks are numbered from 1.

Constraints

1 ≤ n ≤ 10^5
1 ≤ k ≤ 10^5
1 ≤ each duration ≤ 10^4

Input and output

Input: Line 1: n and k Line 2: n durations
Output: n lines: task number and finish time, ordered as described.

Examples

Input 1

5 2
4 2 3 1 5

Output

Tasks 1 and 2 start at 0. Task 2 ends at 2, so task 3 starts at 2 and ends at 5; task 1 ends at 4 and task 4 runs 4–5; task 5 starts at 5 and ends at 10. Ties print in task order.

Input 2

3 5
3 1 2

Output

2 1
3 2
1 3

More slots than tasks: all start at 0.

Show hints

Each new task starts when the earliest-finishing running task ends.
A min-heap of finish times gives that earliest time in O(log k).

Show the explanation

Keep a min-heap of the finish times of running tasks:

The first k tasks start at 0; push their finish times.
Each later task starts at the smallest finish time in the heap (pop it) and pushes its own finish time, start + duration.
Record (finish, task) for every task and sort by finish time, then task number.

Popping the minimum is exactly "the next slot to free up", and start times never decrease, so tasks start in list order as required. With n tasks this is O(n log k) plus the final sort.

The real asynchronous version keeps k workers that each pull the next index from a shared counter:

JavaScript

async function runWithLimit(tasks, k) {
  const results = []; let next = 0;
  const worker = async () => { while (next < tasks.length) { const i = next++; results[i] = await tasks[i](); } };
  await Promise.all(Array.from({ length: Math.min(k, tasks.length) }, worker));
  return results;
}

Because JavaScript is single-threaded, next++ cannot race between workers.

Original UniCircle question. Last reviewed 22 Oct 2026.