FastPrep
Problem · Simulation

Phone Battery Discharge Scheduling

Learn this problem
● MediumRoblox logoRobloxFULLTIMEOA
See Roblox hiring insights

Problem statement

A dead phone needs to run for t minutes of usage time. You have n spare batteries indexed 0 to n - 1, all fully charged at the start. Battery i provides capacity[i] minutes of phone runtime; after it is fully drained it needs recharge[i] minutes of real-time to be ready again.

Batteries must be used in strict cyclic order: 0, 1, 2, ..., n - 1, 0, 1, .... You cannot skip a battery: if the next one in line is still recharging when its turn comes, the phone sits dead (off) until that battery is ready. Phone usage time does not advance while the phone is off; only real-time advances, allowing the other batteries to keep recharging on their own schedules. Once a battery is inserted, the phone runs on it continuously until it is fully drained or the phone hits its t-minute target — you cannot pop a battery out partway through to insert the next one.

Return the indices of the batteries that were fully discharged within the t minutes of usage, in the order they discharged. If the last battery used was only partially drained when the phone hit its t-minute target, it is not included.

Function

batteryDischargeOrder(t: int, capacity: int[], recharge: int[]) → int[]

Examples

Example 1

t = 10capacity = [3, 4, 2]recharge = [5, 6, 8]return = [0, 1, 2]
Battery 0 runs from real-time 0 to 3 (full discharge), battery 1 from 3 to 7 (full discharge), battery 2 from 7 to 9 (full discharge). At real-time 9, battery 0 is back (recharged at 8) and runs for 1 more minute before the phone hits 10 minutes of usage. That is a partial use, so battery 0's second turn is not counted.

Example 2

t = 10capacity = [5]recharge = [5]return = [0, 0]
Battery 0 runs 0..5 (full discharge, ready again at real-time 10). The phone is off from real-time 5 to 10. At real-time 10, battery 0 runs another 5 minutes (full discharge), bringing usage to 10. Battery 0 is fully discharged twice.

Example 3

t = 4capacity = [5]recharge = [10]return = []
Battery 0 provides 5 minutes of capacity but only 4 are used before the phone hits the runtime target. It is only partially drained, so it is never fully discharged and the result is empty.

Constraints

  • 1 <= t <= 10^4
  • 1 <= capacity.length == recharge.length <= 10^3
  • 1 <= capacity[i] <= 10^4
  • 0 <= recharge[i] <= 10^4

More Roblox problems

drafts saved locally
public int[] batteryDischargeOrder(int t, int[] capacity, int[] recharge) {
  // write your code here
}
t10
capacity[3, 4, 2]
recharge[5, 6, 8]
expected[0, 1, 2]
checking account