Count Fully Used Batteries
Learn this problem
MetaINTERNOAProblem statement
Your mobile phone is out of power, but you need to keep it working continuously for t minutes. You have several spare batteries, and all of them are fully charged at time 0.
Battery i can power the phone for capacity[i] minutes. Once it is fully depleted, it must recharge for recharge[i] minutes before it can be used again.
Use the batteries in their given cyclic order. When the current battery is fully depleted, move to the next battery. If that battery is still recharging, skip it and continue checking the following batteries in order. If every battery is recharging when the phone needs another battery, the phone cannot remain on continuously.
Return the number of complete battery usages during the required t minutes. A battery counts each time it is fully depleted. If it is impossible to keep the phone working continuously for all t minutes, return -1.
A solution with time complexity no worse than O(t * capacity.length) will fit within the execution time limit.
Function
solution(t: int, capacity: int[], recharge: int[]) → intExamples
Example 1
t = 16capacity = [2,5,6]recharge = [12,1,4]return = 3- Battery
0powers the phone from time0to time2. It is then depleted, counts as one complete usage, and will be ready again at time14. - Battery
1runs from time2to time7, counts as the second complete usage, and will be ready again at time8. - Battery
2runs from time7to time13, counts as the third complete usage, and will be ready again at time17. - At time
13, battery0is still recharging, so it is skipped. Battery1is ready and supplies the remaining3minutes. Because this final use does not fully deplete battery1, it is not counted.
The phone remains on for all 16 minutes, and the number of complete battery usages is 3.