0397EasyArrayGreedySorting

Seedling Trolley Load

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 nursery wheels plant trays out to the loading dock on a single trolley.

You are given trayTypes, where trayTypes[i] = [count_i, seedlings_i] means the nursery has count_i trays of type i on hand and each of those trays holds exactly seedlings_i seedlings.

The trolley has room for trolleySlots trays altogether. You may put on any mix of types, taking no more of a type than the nursery has, and you are free to leave slots empty.

Return the greatest number of seedlings a single trolley run can carry.

Examples

Example 1

Input: trayTypes = [[2,4],[3,7],[1,2]], trolleySlots = 4
Output: 25

Loading all three trays of type 1 at 7 seedlings each and one tray of type 0 at 4 seedlings uses 4 slots and carries 21 + 4 = 25 seedlings.

Example 2

Input: trayTypes = [[6,3],[2,9]], trolleySlots = 2
Output: 18

Only 2 slots exist, and loading both trays of type 1 carries 9 + 9 = 18 seedlings.

Example 3

Input: trayTypes = [[1,5],[2,8]], trolleySlots = 10
Output: 21

Every tray the nursery has fits, so all 3 trays go on and carry 5 + 8 + 8 = 21 seedlings, leaving 7 slots empty.

Example 4

Input: trayTypes = [[4,6],[5,6],[2,1]], trolleySlots = 7
Output: 42

Types 0 and 1 both hold 6 seedlings per tray, and taking all 4 trays of type 0 plus 3 trays of type 1 fills the 7 slots for 42 seedlings.

Constraints

1 <= trayTypes.length <= 1000
trayTypes[i].length == 2
1 <= count_i, seedlings_i <= 1000
1 <= trolleySlots <= 10^6

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 maximum_units(trayTypes: list[list[int]], trolleySlots: int) -> int:

Java

public int maximumUnits(int[][] trayTypes, int trolleySlots)

The intended approach

Time O(k log k) where k = len(trayTypes)Space O(k) for the sorted copy of trayTypes

Order the tray types by seedlings per tray, richest first, then walk that order filling the trolley. From each type take either everything the nursery has of it or exactly the number of slots still free, whichever is smaller, and stop once no slots remain.

Pythonentry point: maximum_units

def maximum_units(trayTypes, trolleySlots):
    # Time O(k log k) for the sort, k = len(trayTypes); the scan after it is
    # O(k). Space O(k) for the sorted copy of the type list.
    order = sorted(trayTypes, key=lambda pair: -pair[1])
    total = 0
    left = trolleySlots
    for count, seedlings in order:
        if left <= 0:
            break
        take = count if count < left else left
        total += take * seedlings
        left -= take
    return total

The obvious version

Expand every available tray into one entry of its own seedling figure, sort that flat list from high to low, and add up the first trolleySlots entries.

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_maximum_units(trayTypes, trolleySlots):
    every = []
    for count, seedlings in trayTypes:
        for _ in range(count):
            every.append(seedlings)
    every.sort(reverse=True)
    total = 0
    for value in every[:trolleySlots]:
        total += value
    return total

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
4 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