Library Repair Desk Routing

Indices assigned to array durations by lowest load, then lowest index

EasyHeapPriority QueueSimulation

A library has desks book-repair desks, numbered from 0 to desks - 1. Each desk starts with zero minutes of assigned work.

The array durations lists the repair times of books in the order they arrive. Assign each book according to these rules:

  1. Choose the desk with the smallest total duration of work assigned so far.
  2. If several desks have the same total, choose the desk with the smallest number.
  3. Add the book's repair time to that desk's total.

All assignments are made before any repair work begins, so desk totals only increase as books are assigned. A book with duration zero still receives an assignment.

Return an array containing the chosen desk number for each book, in arrival order. If there are no books, return an empty array.

Examples

Example 1

Input: durations = [4,2,3,1,5], desks = 2
Output: [0,1,1,0,0]

The first two books go to different desks because the unused desk has less assigned work. After assigning the third book, the desk totals are four and five minutes, so the fourth book goes to the first desk. That creates a tie, which is resolved by the smaller desk number for the final book.

Example 2

Input: durations = [0,5,0,2], desks = 3
Output: [0,0,1,1]

A zero-minute book does not change its desk's total. The next book therefore encounters the same tie and goes to the smallest-numbered desk again.

Example 3

Input: durations = [], desks = 4
Output: []

With no books to assign, every desk remains unused.

Constraints

  • 0 <= durations.length <= 8500
  • 0 <= durations[i] <= 1000000
  • 1 <= desks <= 8500

The routing rules define a simulation, not an optimization problem. The intended complexity is O(desks + durations.length * log(desks + 1)) time and O(desks) auxiliary space, excluding the returned array.

Hints

Show hint 1

You only need to find the desk with the smallest current total before each assignment.

Show hint 2

Store pairs of assigned duration and desk number in a min-heap, so the tie-breaking rule is part of the ordering.

Follow-up questions

What an interviewer might ask once you have a working solution.

  • How would you change the solution if each desk started with a different amount of assigned work?
  • How would you handle books arriving at specified times while desks complete previously assigned work?

Practice this with an AI interviewer

Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.

Start this problem