Parallel Job Execution Operations
MediumBinary Search · Adobe
You have n jobs, and job i needs times[i] seconds of processing before it is finished. Work happens in discrete operations. In each operation:
- you choose exactly one unfinished job as the major job, and it receives
xseconds of processing; - every other unfinished job receives
yseconds of processing at the same time (y < x).
A job is finished as soon as its total processing reaches at least times[i]; finished jobs receive nothing further and can no longer be chosen.
Return the minimum number of operations needed to finish every job.
Example 1
- Input:
- times = [9, 4, 15], x = 6, y = 2
- Output:
- 4
- Explanation
- In 4 operations every job collects at least 4 * 2 = 8 seconds, and each time a job is major it gets 6 - 2 = 4 seconds extra. Job 0 needs 1 more second (one major turn), job 1 is already done, job 2 needs 7 more (two major turns): 3 major turns fit in 4 operations. With only 3 operations, 4 major turns would be needed, which is too many.
Example 2
- Input:
- times = [7, 7, 7], x = 3, y = 1
- Output:
- 5
- Explanation
- With 5 operations each job passively gets 5 seconds and needs one major turn for the last 2, so 3 major turns fit in 5 operations. With 4 operations each job would need two major turns, 6 in total, which does not fit.
Example 3
- Input:
- times = [100], x = 10, y = 9
- Output:
- 10
- Explanation
- A lone job is the major job every time and gets 10 seconds per operation, so it needs 10 operations.
Constraints
1 <= times.length <= 10^51 <= times[i] <= 10^91 <= y < x <= 10^9