Assume you have a phone, and several spare batteries.

arr1 => denotes the minutes for which every battery can last.

arr2 => denotes the minutes that every battery takes to be fully charged.

• Once the battery is used up, you can charge it immediately and switch to the next fully charged battery.
• You must use the batteries in the order the array denotes.

Suppose you will use the phone for x minute, return the number of batteries you will use.

If it is not possible to use the phone, then return -1

Example:
arr1 = [12, 3, 5, 18]
arr2 = [8, 1, 4, 9]
x = 16 
output: 3

My Code:

arr1 = [12, 3, 5, 18]
arr2 = [8, 1, 4, 9]
x = 46        # getting correct result when x=16 but not when x=46

def solution(arr1, arr2, x):
    import heapq
    ready,charge=list(range(len(arr1))),[]
    heapq.heapify(ready)
    cur=res=0
    while cur<x:    
        while charge and charge[0][0]<=cur:
            heapq.heappush(ready, heapq.heappop(charge)[1])
            
        if not ready:
            return -1
        
        i=heapq.heappop(ready)    
        res  = 1
        cur =arr1[i]
        heapq.heappush(charge,(cur arr2[i],i))
    
    return res

solution(arr1, arr2, x)

The code is giving an output 7.

But, the correct output is 5.

CodePudding user response：

It seems you can implement this by simply looping through the sum of arr1 values until you reach x, maintaining a list of ready times for each battery so you can check whether the battery is currently available to use:

def solution(arr1, arr2, x):
    numb = len(arr1)
    count = 0
    now = 0
    ready = [0, 0, 0, 0]
    while now < x:
        batt = count % numb
        if ready[batt] > now:
            return -1
        now  = arr1[batt]
        ready[batt] = now   arr2[batt]
        count  = 1
    return count

solution([12, 3, 5, 18], [8, 1, 4, 9], 16)
# 3
solution([12, 3, 5, 18], [8, 1, 4, 9], 46)
# 5
solution([12, 3, 2], [6, 1, 1], 20)
# -1

CodePudding user response：

Here's an alternate function which doesn't involve iterating to find the solution. It computes the number of batteries required by looking at the total runtimes of the array of batteries, dividing x by the total runtime of all the batteries and then looking up the index of run time which will cover the balance (x % total_runtime). I've given a few ways of doing that lookup, dependent on what libraries (if any) are available.

In terms of whether the call can be completed, it looks at whether there is sufficient charge time (in the run time for the other batteries) for each battery before it has to be used again. If not, and the battery has to be used more than once, the call cannot be completed.

def solution(arr1, arr2, x):
    # how many batteries?
    numb = len(arr1)
    # make cumulative sum of battery runtimes
    runtimes = [sum(arr1[:i 1]) for i in range(numb)]
    total_runtime = runtimes[numb-1]
    # figure out how many batteries we need
    batts = x // total_runtime * numb
    x = x % total_runtime
    if x > 0:
        batts  = bisect.bisect_left(runtimes, x)   1
        # or
        # batts  = np.searchsorted(runtimes, x)   1
        # or
        # batts  = next(idx   1 for idx, value in enumerate(runtimes) if value >= x)
    # check if any battery we use has a charge time greater than the total runtime of the other batteries
    excess_charge_times = [total_runtime - runtime - arr2[idx] for idx, runtime in enumerate(arr1)]
    # if a battery has to be used more than once and doesn't have enough charge time, fail
    if any(batts > idx   numb and excess_charge_times[idx] < 0 for idx in range(numb)):
        return -1
    return batts