FastPrep

Description

Solutions

Get Minimum Time

🔥 FULLTIME📚RELATED PROBLEMS

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 Description

Complete the function getMinimumTime in the editor below.

getMinimumTime takes the following parameters:

int n: the total number of processes
int high_priority[k]: the indices of the high-priority processes
int normal_time: the time factor for completing non-high-priority processes
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

Example 1:

Input:  n = 4, high_priority = [1], normal_time = 2, priority_time = 2
Output: 6 
Explanation:
   
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