Run the shortest waiting job first
A re-solve is due. Start from a blank template and solve it without the editorial. That is what makes the pattern stick.
The problem
A single worker runs batch jobs one at a time. Job i is [arrives, minutes]: it can start at minute arrives or later and takes minutes to finish.
Whenever the worker is free, it starts the waiting job with the fewest minutes; ties go to the earlier arrival, then the lower position in jobs. If nothing is waiting, it idles until the next job arrives. Return the positions of the jobs in the order they start.
- 0 ≤ jobs.length ≤ 200,000
- 0 ≤ arrives ≤ 10⁹
- 1 ≤ minutes ≤ 10⁴
- jobs are not sorted
Examples
jobOrder([[0, 10], [1, 2], [2, 1], [30, 5]])returns[0, 2, 1, 3]Job 0 runs to minute 10; by then 1 and 2 wait, and 2 is shorter. Then the worker idles until 30.jobOrder([[5, 3], [5, 3], [0, 9]])returns[2, 0, 1]A tie in length and arrival goes to the lower position.jobOrder([])returns[]
Hints
Hint 1 of 2
Sort the jobs by arrival, so you know which ones have arrived by a given minute. Which job to run next is then a question about the waiting ones only.
Hint 2 of 2
Keep the waiting jobs in a min-heap ordered by minutes, then arrival, then position. When the worker is free, add every job that has arrived, then pop the top. If the heap is empty, jump to the next arrival.
Editorial
Opens once you solve the problem, or after three checked attempts.
Read the editorial and a reference solution
This is a simulation with one hard step: picking the shortest waiting job, again and again, while new jobs keep arriving. Scanning the waiting jobs each time is quadratic when many wait at once.
Sort the jobs by arrival once, and keep a pointer into that order. When the worker is free at minute t, push every job that has arrived by t into a min-heap ordered by length, then arrival, then position. Pop the top, run it, and advance t by its length.
If the heap is empty, the worker is idle: jump t forward to the next arrival before pushing. Forgetting this either loops forever or starts a job before it arrives.
Put all three tie rules in the comparison function. A heap does not keep insertion order, so ties that are not in the comparison come out in an order that depends on the heap's internal swaps.
function jobOrder(jobs) {
const byArrival = jobs.map((_, i) => i).sort((a, b) => jobs[a][0] - jobs[b][0] || a - b);
const less = (x, y) => jobs[x][1] - jobs[y][1] || jobs[x][0] - jobs[y][0] || x - y;
const h = [];
const push = (x) => { h.push(x); for (let i = h.length - 1; i > 0;) { const p = (i - 1) >> 1; if (less(h[p], h[i]) <= 0) break; [h[p], h[i]] = [h[i], h[p]]; i = p; } };
const pop = () => {
const top = h[0], last = h.pop();
if (h.length) {
h[0] = last;
for (let i = 0; ;) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < h.length && less(h[l], h[m]) < 0) m = l;
if (r < h.length && less(h[r], h[m]) < 0) m = r;
if (m === i) break;
[h[m], h[i]] = [h[i], h[m]]; i = m;
}
}
return top;
};
const order = [];
let t = 0, k = 0;
while (order.length < jobs.length) {
if (!h.length && k < byArrival.length) t = Math.max(t, jobs[byArrival[k]][0]);
while (k < byArrival.length && jobs[byArrival[k]][0] <= t) push(byArrival[k++]);
const j = pop();
order.push(j);
t += jobs[j][1];
}
return order;
}Complexity. O(n log n) time for the sort and the heap, O(n) space.
Your solution
TypeScript types are removed before the tests run, not checked: the tests judge what the code does.
Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.