Run the shortest waiting job first

HardAbout 40 minProblem 2 of 2 in HeapsDraft

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

  1. 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.
  2. jobOrder([[5, 3], [5, 3], [0, 9]])returns [2, 0, 1]A tie in length and arrival goes to the lower position.
  3. 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.

Your solution

Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.

Esc
↑ ↓ to move↵ to open