0220EasyArrayTwo PointersGreedySortingQuicksort

Scratch Space Handout

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 scheduler is about to launch a queue of jobs on one machine. You are given an integer array need, where need[i] is the amount of scratch memory that job i must be handed before it will launch, and an integer array blocks, where blocks[j] is the size of the j-th free block of scratch memory.

A job launches only if it is handed a single whole block whose size is at least its requirement. Blocks are never split and never shared, so each block goes to at most one job and each job takes at most one block. Some jobs may be left unlaunched.

Return the largest number of jobs that can be launched.

Examples

Example 1

Input: need = [4, 9], blocks = [3, 5, 12]
Output: 2

Hand the 5-unit block to the job that needs 4 and the 12-unit block to the job that needs 9. Both blocks are at least as large as the requirement they cover, so 2 jobs launch.

Example 2

Input: need = [8, 3, 6], blocks = [2, 2, 2]
Output: 0

Every free block holds 2 units, which is below all three requirements, so no job can be handed a block it accepts.

Example 3

Input: need = [5, 1, 5], blocks = [6, 1, 2]
Output: 2

The 1-unit block covers the job that needs 1 and the 6-unit block covers one of the jobs that needs 5. The only block left holds 2 units, which is below the remaining requirement of 5, so that job stays unlaunched and the count is 2.

Constraints

1 <= need.length <= 3 * 10^4
0 <= blocks.length <= 3 * 10^4
1 <= need[i], blocks[j] <= 2^31 - 1

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 max_jobs_started(need: list[int], blocks: list[int]) -> int:

Java

public int maxJobsStarted(int[] need, int[] blocks)

The intended approach

Time O(n log n + m log m)Space O(n + m) for the two sorted copies

Sort a copy of the requirements and a copy of the block sizes, then sweep them together with one index into the block sizes. For each requirement in increasing order, skip the blocks that are too small and consume the first block that fits; a consumed block is never revisited, so the index only moves forward and each list is scanned once after sorting.

Pythonentry point: max_jobs_started

def max_jobs_started(need, blocks):
    wants = sorted(need)
    supply = sorted(blocks)
    started = 0
    j = 0
    for want in wants:
        while j < len(supply) and supply[j] < want:
            j += 1
        if j == len(supply):
            break
        started += 1
        j += 1
    return started

The obvious version

Treat it as a bipartite matching between jobs and blocks: a job may hold any block at least as large as its requirement. Add jobs one at a time and run an augmenting-path search that reshuffles earlier placements when needed, which finds the maximum number of placeable jobs directly.

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_max_jobs_started(need, blocks):
    holder = [-1] * len(blocks)

    def place(job, tried):
        for j, size in enumerate(blocks):
            if size >= need[job] and j not in tried:
                tried.add(j)
                if holder[j] == -1 or place(holder[j], tried):
                    holder[j] = job
                    return True
        return False

    total = 0
    for job in range(len(need)):
        if place(job, set()):
            total += 1
    return total

How this problem was checked

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