Show problems as
Classic problem #2974EasyArraySortingHeap (Priority Queue)Simulation

Minimum Number Game

Real-world version: Shelving Boxes in Turns
Tracked in this browser only
Read Minimum Number Game on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Two archivists, Ada and Ben, clear a pile of boxes. Each box carries a label, given as the list labels, and the pile holds an even number of boxes.

They repeat the following round until the pile is empty:

  1. Ada lifts the box with the smallest label still in the pile.
  2. Ben lifts the box with the smallest label still in the pile.
  3. Ben places his box at the end of the shelf.
  4. Ada places her box at the end of the shelf.

Labels may repeat; when two boxes carry the same label it makes no difference which of them is lifted, because the shelf reads the same either way.

Return the list of labels along the shelf, from the first box placed to the last.

Examples

Example 1

Input
labels = [12, 9, 4, 30]
Output
[9, 4, 30, 12]

Round one: Ada lifts `4`, Ben lifts `9`, so the shelf starts `9`, `4`. Round two: Ada lifts `12`, Ben lifts `30`, so the shelf continues `30`, `12`.

Example 2

Input
labels = [8, 6, 6, 8, 6, 8]
Output
[6, 6, 8, 6, 8, 8]

The first two rounds each lift a `6` and a `6`, and a `6` and an `8`; the last round lifts the remaining two `8`s. Placing each round's second box first gives the shelf shown.

Example 3

Input
labels = [100, 1, 2, 99]
Output
[2, 1, 100, 99]

Ada lifts `1` and Ben lifts `2` in the first round, then Ada lifts `99` and Ben lifts `100`. Ben places before Ada each round.

Constraints

  • 2 <= labels.length <= 100
  • 1 <= labels[i] <= 100
  • labels.length is even.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def shelve_boxes(labels: list[int]) -> list[int]:
Java
public int[] shelveBoxes(int[] labels)

More on the same topics