Show problems as
Classic problem #455EasyArrayTwo PointersGreedySortingQuicksort

Assign Cookies

Real-world version: Scratch Space Handout
Tracked in this browser only
Read Assign Cookies on LeetCode(opens in a new tab)

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

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

Python
def max_jobs_started(need: list[int], blocks: list[int]) -> int:
Java
public int maxJobsStarted(int[] need, int[] blocks)

More on the same topics