Get Minimum Time
Salesforce● HardFULLTIMEOAProblem 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,p1andp2, such thatp = [p1, p2]. The scheduler will then allocatep1to one processor andp2to 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_timeseconds 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, wherelis 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:
int n: the total number of processesint high_priority[k]: the indices of the high-priority processesint normal_time: the time factor for completing non-high-priority processesint 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 = 6One 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^9nis a power of 21 ≤ k ≤ min(n, 10^5)1 ≤ high_priority[i] ≤ n