Amazon Online Assessment (OA) - Multiprocessor System
Multiprocessor systems involve multiple CPUs for performing various tasks, which increases throughput and reduces response time. A multiprocessor system has a certain number of processors. Each processor has the ability to schedule a limited number of processes in one second. However, after each scheduling, the processor's ability is reduced to ability/2 rounded down to the nearest number. Only one processor can work to schedule processes each second. As an Amazonian you are tasked to find the minimum time required to schedule all the processes in the system given the processor's abilities and the number of processes.
Write an algorithm that returns minimum time required to schedule the processes.
Input
The input to the function/method consists of three arguments:
num : an integer representing the number of processors
ability: a list of integers representing the ability of the processors
processes: a long integer representing the number of processes to be scheduled.
Output
Return an integer representing the minimum time required to schedule the processes.
Constraints
1 <= num <= 10^51 <= ability[i] <= 10^61 <= processes <= 10^120 <= i < num
Note
It is guaranteed that the processes can be scheduled using the given multiprocessor system.
Examples
Example 1:
Input: num = 5, ability = [3, 1,7,2,4], processes = 15
Output: 4
Explanation:
This can be solved optimally in the following way:
First, the processor with ability = 7 schedules 7 processes in one second. Now, ability = [3, 1, 3, 2, 4] because 7 was reduced to floor(7/2).
Second, the processor with ability = 4 is used. After that, ability = [3,1,3,2,2].
Third, the processor with ability = 3 is used. Now, ability = [1, 1, 3, 2, 2].
Finally, the processor with ability = 1 is used to schedule the final process.
Each step requires one second of processing time, which adds up to 4.
So, the output is 4.