0714MediumArrayTwo PointersGreedySorting

Slotting Machines Against The Rival Bench

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def slot_machines(mine: list[int], rival: list[int]) -> list[int]:

Java

public int[] slotMachines(int[] mine, int[] rival)

The intended approach

Time O(n log n) for n slots: two sorts and n binary searches, plus near-constant amortised work per hop through the forwarding table.Space O(n) for the sorted copy of our figures, the forwarding table and the returned booking.

Sorting both figure lists gives the number of slots that can be won: sweep the rival figures from smallest to largest with one forward-only pointer into our sorted machines, taking the weakest machine that clears each rival figure. That count fixes how many slots have to be lost. The answer is then filled slot by slot in the comparison order, rivals strongest first: while lost slots are still owed, the weakest machine left goes in, which is both the smallest figure available and the least useful one elsewhere; once no lost slots remain, every later slot must be won and takes the weakest machine left that clears its rival figure, found by a binary search for the figure followed by a hop past the machines already booked. Those hops go through a forwarding table where each used position points one step on, with the chain flattened as it is walked, so the hops cost almost nothing overall and no machine is ever shifted inside the sorted copy.

Pythonentry point: slot_machines

def slot_machines(mine, rival):
    # Sort our machines ascending and walk the rival figures from strongest down.
    # The number of slots that can be won is fixed, so the number that must be lost
    # is fixed too; spend those losses on the strongest rivals with the weakest
    # machines, then every later slot has to be won and takes the weakest machine
    # that clears its rival.  Machines are never removed from the sorted copy, they
    # are marked used in a forwarding table so a binary search can skip past them.
    # Time O(n log n) for n slots; space O(n) for the sorted copy, the forwarding
    # table and the answer.
    from bisect import bisect_right

    n = len(mine)
    ours = sorted(mine)
    p = 0
    wins = 0
    for figure in sorted(rival):
        while p < n and ours[p] <= figure:
            p += 1
        if p == n:
            break
        p += 1
        wins += 1
    losses = n - wins

    forward = list(range(n + 1))

    def first_free(start):
        root = start
        while forward[root] != root:
            root = forward[root]
        step = start
        while forward[step] != root:
            forward[step], step = root, forward[step]
        return root

    order = sorted(range(n), key=lambda i: (-rival[i], i))
    answer = [0] * n
    for taken, i in enumerate(order):
        if taken < losses:
            spot = taken
        else:
            spot = first_free(bisect_right(ours, rival[i]))
        answer[i] = ours[spot]
        forward[spot] = spot + 1
    return answer

The obvious version

Enumerate every distinct booking of our machines, count the slots each one wins, and keep the booking that wins the most, settling ties by the comparison the problem defines. Factorial in the number of slots, so it only runs on a handful of machines, but it assumes nothing about sorting or matching.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_slot_machines(mine, rival):
    from itertools import permutations

    n = len(mine)
    order = sorted(range(n), key=lambda i: (-rival[i], i))
    best_wins = -1
    best_reading = None
    best = None
    for cand in set(permutations(mine)):
        wins = 0
        for a, b in zip(cand, rival):
            if a > b:
                wins += 1
        reading = tuple(cand[i] for i in order)
        if wins > best_wins or (wins == best_wins and reading < best_reading):
            best_wins = wins
            best_reading = reading
            best = cand
    return list(best)

How this problem was checked

Reference solution executed against 18 test cases — 18 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in