Leetcode 875. Koko Eating Bananas

Problem

You are given an array of integers tasks where each element represents the size of a task that needs to be processed, and an integer timeLimit representing the maximum number of hours available.

You can process tasks at any rate k (tasks per hour), where k is a positive integer. When processing a task of size s at rate k, it takes ceil(s / k) hours to complete (rounded up to the nearest integer).

Find the minimum rate k such that all tasks can be processed within the given timeLimit hours.

Requirements

1. Return the minimum positive integer rate k
2. The total time to process all tasks at rate k must not exceed timeLimit
3. Time for each task is calculated as ceil(task_size / k)
4. All tasks must be processed sequentially

Constraints

• 1 ≤ tasks.length ≤ 10⁴
• 1 ≤ tasks[i] ≤ 10⁹
• 1 ≤ timeLimit ≤ 10⁹
• The answer is guaranteed to fit in a 32-bit integer
• Time complexity should be better than O(n × max(tasks))

Examples

Example 1:

` Input: tasks = [3, 6, 7, 11], timeLimit = 8 Output: 4 Explanation:

• At rate 4: ceil(3/4) + ceil(6/4) + ceil(7/4) + ceil(11/4) = 1 + 2 + 2 + 3 = 8 hours
• At rate 3: ceil(3/3) + ceil(6/3) + ceil(7/3) + ceil(11/3) = 1 + 2 + 3 + 4 = 10 hours (too slow) `

Example 2:

` Input: tasks = [30], timeLimit = 10 Output: 3 Explanation:

• At rate 3: ceil(30/3) = 10 hours (exactly at limit)
• At rate 2: ceil(30/2) = 15 hours (exceeds limit) `

Example 3:

Input: tasks = [1, 1, 1, 1, 1], timeLimit = 5 Output: 1 Explanation: At rate 1, each task takes exactly 1 hour, totaling 5 hours.

Hint 1: Search Space The minimum rate must be at least 1, and the maximum useful rate would be the size of the largest task (any faster won't reduce time further for that task). What search technique works well on a sorted range of possible answers?

Hint 2: Monotonic Property If a rate k allows you to finish within the time limit, will any rate greater than k also work? If a rate k is too slow, will any rate less than k also be too slow? This monotonic property is key to an efficient solution.

Hint 3: Checking Validity For a given rate k, how can you quickly check if all tasks can be completed within the time limit? You'll need to sum up the ceiling division for each task.

Full Solution `` Approach:

The key insight is that the relationship between processing rate and total time is monotonic: as the rate increases, the total time required decreases (or stays the same). This makes binary search the optimal approach.

1. Search Space: The minimum rate is 1, and the maximum useful rate is max(tasks) (processing faster than the largest task won't help for that task).
2. Binary Search: For each candidate rate k, we check if all tasks can be completed within the time limit by summing ceil(task / k) for all tasks.
3. Validation Function: The canFinish function calculates the total time needed at a given rate. We use ceiling division to account for partial hours.
4. Optimization: If at any rate we can finish within the time limit, we try to find an even slower (smaller) rate. If we can't finish, we need a faster rate.

Time Complexity: O(n log m) where n is the number of tasks and m is the maximum task size. We perform binary search (log m iterations) and check all tasks in each iteration (n operations).

Space Complexity: O(1) - only using a constant amount of extra space.

import math

def minProcessingRate(tasks, timeLimit):
    """
    Find minimum rate to process all tasks within time limit.
    Uses binary search on the rate, checking if each candidate rate works.
    
    Time: O(n log m) where n = len(tasks), m = max(tasks)
    Space: O(1)
    """
    def canFinish(rate):
        """Check if we can finish all tasks at given rate within timeLimit"""
        totalTime = 0
        for task in tasks:
            # Calculate hours needed for this task at current rate
            # Using math.ceil or integer division trick: (task + rate - 1) // rate
            totalTime += math.ceil(task / rate)
            # Early exit if already exceeded
            if totalTime > timeLimit:
                return False
        return totalTime <= timeLimit
    
    # Binary search bounds
    left = 1  # Minimum possible rate
    right = max(tasks)  # Maximum useful rate
    result = right
    
    while left <= right:
        mid = (left + right) // 2
        
        if canFinish(mid):
            # This rate works, try to find a slower (smaller) rate
            result = mid
            right = mid - 1
        else:
            # This rate is too slow, need faster rate
            left = mid + 1
    
    return result