FastPrep
Problem · Recursion

Get Minimum Time

Learn this problem
● HardSalesforceFULLTIMEOA
See Salesforce hiring insights

Problem statement

Given n processes that need to be executed. Among these n processes, k are classified as high-priority processes, with their indices (1-based) represented in the array as high_priority[i].

An OS scheduler is responsible for overseeing the execution of all processes. When a scheduler assigns a set of processes to a processor, it has two options:

  • If the assigned processes are greater than 1 and even, it can divide the array of processes, denoted as p, into two contiguous subarrays of equal length, p1 and p2, such that p = [p1, p2]. The scheduler will then allocate p1 to one processor and p2 to another.
  • Alternatively, the scheduler can choose to execute the assigned array of processes, p. The time required for process execution is determined based on the following criteria:

    👉 1. If the assigned processes do not include any high-priority processes, the scheduler will take normal_time seconds to complete all the assigned processes.

    👉 2. If there are high-priority processes among the assigned tasks (denoted as x), it will take (priority_time * x * l) seconds to complete them, where l is the total number of assigned processes.

    • The total time required to execute all processes is the sum of the time taken by all processors for their assigned tasks. The task is to minimize the total execution time by optimizing the assignment of processes to processors within the operating system and return this minimum possible execution time.

    Function

    getMinimumTime(n: int, high_priority: int[], normal_time: int, priority_time: int) → int

    Complete the function getMinimumTime in the editor below.

    getMinimumTime takes the following parameters:

    1. int n: the total number of processes
    2. int high_priority[k]: the indices of the high-priority processes
    3. int normal_time: the time factor for completing non-high-priority processes
    4. int priority_time: the time factor for completing high-priority processes

    Returns

    int: the minimum total execution time by optimizing the assignment of processes to processors within the operating system

    Examples

    Example 1

    n = 4high_priority = [1]normal_time = 2priority_time = 2return = 6
    One of the optimal ways is as follows:
  • Assign a processor to [1, 2], which will execute the processes in (2 * 1 * 2) = 4 seconds.
  • Assign a processor to [3, 4], which will execute the processes in 2 seconds.
    • Hence, the total time taken is 6 seconds.

    Constraints

    • 1 ≤ n ≤ 10^9
    • n is a power of 2
    • 1 ≤ k ≤ min(n, 10^5)
    • 1 ≤ high_priority[i] ≤ n

    More Salesforce problems

    drafts saved locally
    public int getMinimumTime(int n, int[] high_priority, int normal_time, int priority_time) {
  // write your code here
}
    n4
    high_priority[1]
    normal_time2
    priority_time2
    expected6
    checking account