Practice/Oracle/Leetcode 875. Koko Eating Bananas

Leetcode 875. Koko Eating Bananas

CodingMust

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.