The algorithm for the maxRunTime() function can be summarized as follows:
- Calculate the sum of all batteries.
- Initialize the start time and end time to 0 and the sum of all batteries, respectively.
- Initialize the answer to 0.
- While the start time is less than or equal to the end time:
- Calculate the average of the start time and end time.
- If the average is feasible, then:
- Set the answer to the average.
- Set the start time to the average plus 1.
- Otherwise:
- Set the end time to the average minus 1.
- Return the answer.
The runFeasible() function checks if the average run time is feasible. It does this by calculating the total time that all of the batteries can run for at the average run time. If the total time is greater than or equal to the average run time multiplied by the number of batteries, then the average run time is feasible. Otherwise, the average run time is not feasible.
for example, consider the following input:
n = 3 batteries = [1, 2, 3]
The sum of all batteries is 6. The start time and end time are initialized to 0 and 6, respectively. The answer is initialized to 0.
The while loop is executed like this:
| Iteration | Start time | End time | Average | Feasible? | Action |
|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | Yes | Set answer to 3. Set start time to 4. |
| 2 | 4 | 3 | 3.5 | Yes | Set answer to 3.5. Set start time to 4.5. |
| 3 | 4.5 | 3 | 3.75 | No | Set end time to 3. |
| 4 | 4 | 3 | 3.5 | Yes | Set answer to 3.5. Set start time to 4.5. |
| 5 | 4.5 | 3 | 3.75 | No | Set end time to 3. |
The while loop terminates because the start time is now greater than the end time. The answer is 3.5.