Minimum Grading Speed
MediumExtra practice. This problem has no walkthrough slides. Try solving it with the pattern template on your own, and lean on the hints if you get stuck.
Question
You're a teacher with several stacks of ungraded exams on your desk. Each stack holds some number of exams. You'll grade at a constant rate of k exams per hour, working through one stack completely before starting the next.
Grading a stack always costs a whole number of hours: if any exams are left in a stack after applying your rate for an hour, that costs a full extra hour on that same stack. Leftover grading time never carries over into the next stack.
Given the stacks and a number of hours before grades are due, return the minimum constant rate k that lets you finish every stack in time.
Input: stacks = [10, 20, 30], hours = 6
Output: 10
At a rate of 10, grading takes 1 + 2 + 3 = 6 hours, which just fits. A rate of 9 would take 2 + 3 + 4 = 9 hours, which is too slow.
Input: stacks = [3, 6, 7, 11], hours = 8
Output: 4
At a rate of 4, grading takes 1 + 2 + 2 + 3 = 8 hours. A rate of 3 would take 1 + 2 + 3 + 4 = 10 hours, which misses the deadline.
Input: stacks = [1, 1, 1, 1], hours = 4
Output: 1
There are exactly as many hours as stacks, so even the slowest rate of 1 exam per hour is enough.
You might also hear this problem called “Koko Eating Bananas.”
Clarify the problem
What are some questions you'd ask an interviewer?
Understand the problem
Take a moment to understand the problem and think of your approach before you start coding.