FastPrep
Problem · Binary Search

Job Execution

Learn this problem
● HardSnowflakeINTERNOA
See Snowflake hiring insights

Problem statement

There are n jobs that can run in parallel on a processor. The execution time of job j is executionTime[j].

In one operation, choose one job as the major job. The major job executes for x seconds, and every other unfinished job executes for y seconds, where y < x.

A job is complete once it has executed for at least executionTime[i] seconds, after which it exits the pool. Find the minimum number of operations needed to complete all jobs when the processor is used optimally.

Complete getMinimumOperations with the following parameters:

  • int executionTime[n]: the execution times of the jobs
  • int x: the time given to the major job in one operation
  • int y: the time given to every other unfinished job

Returns: int, the minimum number of operations needed to complete all jobs.

Function

getMinimumOperations(executionTime: int[], x: int, y: int) → int

Examples

Example 1

executionTime = [3, 4, 1, 7, 6]x = 4y = 2return = 3

Using 1-based job indexes, the following three operations are optimal:

  1. Choose job 4. The remaining times become [1, 2, -1, 3, 4].
  2. Choose job 5. The remaining times become [-1, 0, -3, 1, 0].
  3. Choose job 4. Every remaining time is now at most 0.

All jobs finish after 3 operations.

Constraints

  • 1 ≤ n ≤ 10^5
  • 1 ≤ executionTime[i] ≤ 10^9
  • 1 ≤ y < x ≤ 10^9

More Snowflake problems

drafts saved locally
public int getMinimumOperations(int[] executionTime, int x, int y) {
  // write your code here
}
executionTime[3, 4, 1, 7, 6]
x4
y2
expected3
checking account