Find the Minimum Processing Rate to Meet a Deadline

Problem Statement

You are managing a server cluster tasked with processing a series of independent workloads. You are given a list of integers workloads, where workloads[i] represents the amount of data (in units) that must be processed for the i-th task. You are also given an integer deadline (in hours).

Each workload must be completed within the deadline. The server processes data at a fixed constant rate of k units per hour. Crucially, each workload is processed independently: if a workload is not a perfect multiple of k, the server must spend an additional hour to process the remainder. For example, if a workload is 10 units and the rate k is 3, it will take 4 hours to complete (3+3+3+1).

Find the minimum integer rate k (units/hour) such that the sum of the hours required for all tasks does not exceed the deadline.

Function Signature

def min_processing_rate(workloads: List[int], deadline: int) -> int:

Constraints

• 1 <= len(workloads) <= 10^5
• 1 <= workloads[i] <= 10^9
• len(workloads) <= deadline <= 10^12

Examples

Example 1:

• Input: workloads = [3, 6, 7, 11], deadline = 8
• Output: 4
• Explanation: If k=4, hours = ceil(3/4) + ceil(6/4) + ceil(7/4) + ceil(11/4) = 1 + 2 + 2 + 3 = 8. Since 8 <= 8, this is valid.

Example 2:

• Input: workloads = [30, 11, 23, 4, 20], deadline = 5
• Output: 30

Edge Cases

• If the number of tasks exceeds the deadline, it is impossible to finish, even with infinite processing power. In this case, return -1.
• workloads values can be very large; ensure your calculations handle potential overflows.