Problem Statement :

Edward and Alphonse are alchemists. They want to perform human transmutation to revive their mother and need philosopher stones for it. Father Inc has a factory which produces philosopher stones. The factory will run for n days. On day i the factory will produce A[i] stones. These stones also have a expiry date! The stones produced on day i can only be used for D[i] days. So if D[i] = 1 those stones can only be used on the day they are produced and so on.

Edward and Alphonse want to maximise their chances to succeed at the transmutation. For this tell them the maximum number of stones they can use for the transmutation.

[execution time limit] 4 seconds (py3)

[input] array.integer stones

This is an array of the number of stones produces on day i. 0 <= stones[i] <= 10000000. No of array elements <= 100000

[input] array.integer days

This is an array of the number of days stones produces on day i can be used for. 0 <= days[i] <= 1000000. No of array elements <= 100000

[output] integer

Output an integer which is the maximum number of stones that can be used for the transmutaion.As the answer can be large give the result modulo 1000000007.

Solution :

A Brute force O(N^2) solution is obvious.
A more efficient solution can be using a minheap. Since the heap will have at most n number of elements where n is length of stones array. Time complexity will be O(nlogn).
My Solution in Python:

def countingStonesHire2020(stones, days):
    heap = []
    import heapq
    cs = 0
    ms = 0
    n = len(stones)
    
    for i in range(n):
        cs += stones[i]
        reach = i+days[i]-1
        while True:
            if heap and heap[0][0] < i:
                lr,ind = heapq.heappop(heap)
                cs -= stones[ind]
            else:
                break
        heapq.heappush(heap, (reach,i))
        ms = max(ms,cs)
    return ms%(10**9+7)

Please suggest some alternative approaches to solve the problem.

Test Cases -

1. stones = [4,1,2,1,2], days = [1,4,5,1,5] Output = 5
2. stones = [92,55,51,41,56], days = [4,5,5,3,1] Output = 239