Place books on the least-full allowed shelf

You have num_shelves shelves, numbered 0 to num_shelves - 1. All shelves start empty.

Books arrive one at a time. Book i comes with a limit limits[i]. It may only go on shelves 0 through limits[i] - 1. Among those shelves, put it on the shelf that currently holds the fewest books. If several shelves tie, choose the one with the smallest index. Then the next book arrives.

Implement:

def organize_books(num_shelves: int, limits: list[int]) -> list[int]:
    ...

Return a list with the shelf index each book was placed on, in arrival order.

Constraints

• 1 <= num_shelves <= 10^5
• 0 <= len(limits) <= 10^5
• 1 <= limits[i] <= num_shelves

A solution that scans the allowed shelves for every book is too slow at these sizes.

Example 1

num_shelves = 3, limits = [3, 3, 3, 3]
output: [0, 1, 2, 0]

Every book may use all three shelves, so they fill round-robin. The fourth book sees counts [1, 1, 1] and takes shelf 0 by the tie-break.

Example 2

num_shelves = 4, limits = [1, 2, 2, 4, 4]
output: [0, 1, 0, 2, 3]

Book 0 must use shelf 0. Book 1 picks shelf 1 (0 books). Book 2 sees counts [1, 1] on shelves 0..1 and takes shelf 0. Books 3 and 4 fill the empty shelves 2 and 3.

Reconstructed from the reported question; details may differ from what interviewers ask.