Show problems as
Classic problem #870MediumArrayTwo PointersGreedySorting

Advantage Shuffle

Real-world version: Slotting Machines Against The Rival Bench
Tracked in this browser only
Read Advantage Shuffle on LeetCode(opens in a new tab)

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

A trade fair runs a head-to-head bench test. There is one slot per machine on each side, and rival[i] is the throughput figure of the rival machine already booked into slot i. The rival booking is published and cannot be changed. mine lists the throughput figures of our own machines, and we may book our machines into the slots in any order we like, one machine per slot.

A slot is won when the figure of our machine in it is strictly greater than the figure of the rival machine in it. Equal figures are not a win.

Return a booking, as an array whose entry i is the figure of the machine we put in slot i, that wins as many slots as possible.

Several bookings may win that same number of slots, so exactly one of them is asked for. Compare two bookings like this: take the slots in decreasing order of their rival figure, putting the earlier slot first when two rival figures are equal, read off the figure each booking put into each of those slots, and at the first place where the two readings differ the booking with the smaller figure there is the smaller booking. Return the smallest booking that wins as many slots as possible.

Examples

Example 1

Input
mine = [6, 3, 9], rival = [4, 4, 4]
Output
[3, 6, 9]

In this booking slot 1 holds our 6 and slot 2 holds our 9, and each of those clears the rival figure of 4, so two slots are won; slot 0 holds our 3, which does not clear 4. All three rival figures are equal, so the comparison reads the slots in the order 0, 1, 2, giving 3, 6, 9.

Example 2

Input
mine = [5, 5], rival = [5, 5]
Output
[5, 5]

Every figure on both benches is 5, so whichever way our machines are booked each slot pairs 5 against 5, and equal figures are not a win, so no slot is won.

Example 3

Input
mine = [2, 8], rival = [7, 3]
Output
[2, 8]

Slot 1 holds our 8 against a rival figure of 3, which is a win, and slot 0 holds our 2 against a rival figure of 7, which is not, so one slot is won. Slot 0 has the larger rival figure, so the comparison reads slot 0 first, giving 2, 8.

Constraints

  • 1 <= mine.length <= 10^5
  • rival.length == mine.length
  • 0 <= mine[i], rival[i] <= 10^9

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 slot_machines(mine: list[int], rival: list[int]) -> list[int]:
Java
public int[] slotMachines(int[] mine, int[] rival)

More on the same topics