How should I practice Process Scheduling?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Blackrock phone screen problems in FastPrep.

Is Process Scheduling associated with Blackrock?

FastPrep tags this as a Blackrock phone screen coding practice problem when the problem catalog has that company and stage context.

Problem

Process Scheduling

Learn this problem

BlackrockFULLTIMEPHONE SCREEN

Problem statement

A scheduling system contains several processors. ability[i] represents the maximum number of processes the i-th processor can schedule in one second at its current ability.

Scheduling is sequential: in each second, choose exactly one processor to use. That processor may schedule up to its current ability, or fewer if fewer processes remain. Immediately after that second, the used processor's ability becomes floor(current ability / 2). The processor remains available with this reduced ability and may be chosen again in a later second. Processors that are not chosen in a second keep their current ability unchanged.

If a processor's ability becomes 0, it cannot schedule any more processes. In particular, ability 1 becomes 0 after one use; it does not keep scheduling one process forever. Therefore, each processor has finite total capacity across all future uses: a + floor(a/2) + floor(a/4) + ... until the value becomes 0.

Given the initial processor abilities and the total number of processes that must be scheduled, return the minimum number of seconds required to schedule all processes. Do not treat all processors as working in parallel during the same second.

Function

minimumSchedulingTime(ability: int[], processes: long) → int

Examples

Example 1

ability = [3,1,7,2,4]processes = 15return = 4

Use one processor per second. One optimal sequence schedules 7, then 4, then 3, then the final 1 remaining process with any processor whose current ability is at least 1. The remaining process count becomes 8, then 4, then 1, then 0, so the answer is 4. Processors used at ability 1 become 0 afterward.

Example 2

ability = [5,3]processes = 8return = 2

Use the processor with ability 5 in the first second and the processor with ability 3 in the second second. Only one processor is used per second, so the answer is 2.

Constraints

1 <= ability.length <= 2 * 10^5
1 <= ability[i] <= 10^9
1 <= processes <= 10^18
It is guaranteed that processes is no larger than the finite total schedulable capacity sum(a + floor(a/2) + floor(a/4) + ...) across all processors.