Minimize Max Processor Time
Phonepe is enhancing its real-time payment settlement infrastructure to handle peak loads more efficiently. A critical component involves processing large batches of pending transactions. Each transaction has a specific, immutable processing duration. To optimize throughput and minimize latency, these transactions must be distributed among a fixed number of parallel processing units. The goal is to find the most efficient distribution such that the maximum time any single processing unit is busy is minimized. This problem directly impacts system performance and user experience during high-volume periods.
You are tasked with implementing a function that determines the minimum possible value for the maximum processing time any single unit will experience.
minMaxProcessorTime function.Function Signature:
function minMaxProcessorTime(transactionDurations: number[], numProcessors: number): number
transactionDurations: An array of positive integers, where transactionDurations[i] represents the time required to process the i-th transaction.numProcessors: A positive integer representing the number of parallel processing units available.Return Value:
numProcessors is 1, all transactions must be processed by that single unit, so the minimum maximum time is the sum of all transaction durations.numProcessors is equal to transactionDurations.length, each transaction can be assigned to its own processor. In this scenario, the minimum maximum time will be the duration of the longest single transaction.Examples
Example 1
Input:
transactionDurations = [10, 20, 30, 40], numProcessors = 2
Output:
60
Note:
With 2 processors, we can split tasks as [10, 20, 30] (total 60) and [40] (total 40). The maximum time for any processor is 60. It's impossible to achieve a maximum time less than 60.
Example 2
Input:
transactionDurations = [1, 2, 3, 4, 5, 6, 7, 8, 9], numProcessors = 3
Output:
17
Note:
Tasks can be distributed as: P1: [1, 2, 3, 4, 5] (sum=15), P2: [6, 7] (sum=13), P3: [8, 9] (sum=17). The maximum time is 17. Any distribution resulting in a max time less than 17 would require more than 3 processors.
Example 3
Input:
transactionDurations = [100, 20, 50], numProcessors = 3
Output:
100
Note:
Since there are 3 processors and 3 transactions, each transaction can be assigned to its own processor. The maximum time will be the duration of the longest transaction, which is 100.
Constraints
1 <= transactionDurations.length <= 10^51 <= transactionDurations[i] <= 10^91 <= numProcessors <= transactionDurations.lengthtransactionDurations will not exceed 10^{14}.transactionDurations[i] are integers.check function (the canProcess helper).Loading editor...