Loading page…
Practice problem · easy
You work on the engineering platform behind an app. A scheduler has a pool of build servers and a queue of jobs. Each server has some memory, and each job needs a minimum amount of memory to run. A server can run at most one job, and a job runs on at most one server.
Your team lead asks: "How many jobs can run at the same time?"
Write most_jobs_placed(servers, jobs).
servers[i] is the memory of server i.jobs[j] is the memory that job j needs.Input: servers = [8, 2, 16, 4], jobs = [5, 3, 12, 1, 9]
Output: 4Sort both lists: servers [2, 4, 8, 16] and jobs [1, 3, 5, 9, 12]. Go through the servers from smallest to largest. Each server takes the smallest job still waiting, if it fits.
| Server | Smallest waiting job | Fits? | Jobs placed |
|---|---|---|---|
| 2 | 1 | yes | 1 |
| 4 | 3 | yes | 2 |
| 8 | 5 | yes | 3 |
| 16 | 9 | yes | 4 |
The job that needs 12 never gets a server, because all four servers are used. The answer is 4.
Input: servers = [3, 3], jobs = [5, 6, 7]
Output: 0No server has enough memory for even the smallest job, which needs 5.
Input: servers = [10, 1, 5], jobs = [2, 2]
Output: 2The server with memory 1 is too small for both jobs. The servers with 5 and 10 each take one job.
0 ≤ len(servers), len(jobs) ≤ 100,0001 ≤ servers[i], jobs[j] ≤ 1,000,000,000There can be 100,000 servers and 100,000 jobs. Trying every way to match jobs to servers is far too slow, because the number of ways grows faster than any power of the input size. A sort costs about 1.7 million steps for each list, and one pass over the sorted lists costs about 200,000 steps more. That fits easily.
most_jobs_placed · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.