FastPrep
Problem Β· Binary Search

Get Min Operations

● HardCitadelINTERNOA

There are n jobs that can be executed in parallel on a processor, where the execution time of the ith job is executionTime[i]. To spped up execution, the following strategy is used.

In one operation, a job is chosen, the major job, and is executed for x seconds. All other jobs are executed for y seconds where y < x.

A job is complete when it has been executed for at least executionTime[i] seconds, the it exits the pool. Find the min num of operations in which the processor can completely execute all the jobs if run optimally.

Function Description

Complete the function citadelGetMinOperations in the editor πŸ‘‰πŸ‘‰.

citadelGetMinOperations has the following parameters:

  1. int executionTime[n]: the execution times for each job
  2. int x: the time for which the major job is executed
  3. int y: the time for which all other jobs are executed executed

Returns

int: the min number of operations in which the processor can complete the jobs

P.S. I'll hold off on uploading the source image for now since it needs too much mosaic effect to hide the sensitive information, and I'm feeling a bit lazyyy πŸ›΅ I am 1000% sure everything matches the original source 😘 GOOOD LUCK, my Citadel friends! >~<

Key insight:

  • _optimization_

    • ♫⋆ｑβ™ͺ β‚ŠΛšβ™¬ ﾟ🐳 Credit to da best, rachel and Aura Man! You both are truly amazing!!ΛšπŸ¦‹α°.ᐟ

    Examples
    01 Β· Example 1
    executionTime = [3, 4, 1, 7, 6]
x = 4
y = 2
return = 3
    The following strategy is optimal using 1-based indexing. * Choose job 4 as the major job and reduce the execution times of job 4 by x = 4 and of other jobs by y = 2. Now executionTime = [1, 2, -1, 3, 4]. Job 3 is complete, so it is removed. πŸ˜€ * Choose job 4, executionTime = [-1, 0, -, -1, 2]. So jobs 1, 2, and 4 are now complete :) * Choose job 5, executionTime = [-, -, -, -, -2]. Job 5 is complete. πŸ’ƒπŸ•Ί It takes 3 operations to execute all the jobs so the answer is 3.
    02 Β· Example 2
    executionTime = [3, 3, 6, 3, 9]
x = 3
y = 2
return = 3
    * Choose job 5, then executionTime = [1, 1, 4, 1, 6]. All jobs are still in the pool 🫨 * Choose job 5, then executionTime = [-1, -1, 2, -1, 3]. So jobs 1,2 and 4 are complete. 🍻 * Choose job 5, then executionTime = [-, -, 0, -, 0]. Jobs 3 and 5 are complete.😍
    03 Β· Example 3
    executionTime = [2, 3, 5]
x = 3
y = 1
return = 3
    * Choose job 3, then executionTime = [1, 2, 2]. All jobs are still in the pool 🀧 * Choose job 3, then executionTime = [0, 1, -1]. So jobs 1 and 3 are complete. πŸ₯‚ * Choose job 2, then executionTime = [-, -2, -]. Jobs 2 is complete.😘
    Constraints
    • 1 <= n <= 3 * 10^5
    • 1 <= executionTime[i] <= 10^9
    • 1 <= y < x <= 10^9
    More Citadel problems
    drafts saved locally
    public int citadelGetMinOperations(int[] executionTime, int x, int y) {
  // write your code here :)
}
    executionTime[3, 4, 1, 7, 6]
    x4
    y2
    expected3
    sign in to submit