Trying to find an optimal solution to a competitive problem, looks like a heap problem

Question

I have a list called examTime = [3, 3, 6, 3, 9], a = 3, b = 2.

Constraints:

• 1<=len(examTime)<=10^5
• 1<=examTime[i]<=10^9
• 1<=b<a<=10^9

My task is to subtract the max element from the examTime by a and other times by b and repeat this operation until all the examTime <= 0 which mean the exams should be finished.

eg.

Step 1: subtract 9 - 3, and others from b new examTime = [1, 1, 4, 1, 6]

Step 2: subtract 6 - 3, and others from b new examTime = [-1, -1, 2, -1, 3]

Step 3: subtract 3 - 3, and others from b new examTime = [-, -, 0, -, 0] So it took 3 operations to finish all the exams.

TC: O((nlogn))

I was using a heap to find the max time and follow this operations but since the constraints are high it doesn't return result and TimeOut exceeds. Is there any other way to solve this problem?

Edit: Adding more details as requested in the comments: Algo:

func minOps(examTime, x, y){
    1. convert all the times to negative in examTime
    2. Heapify
    3. Loop while heap
          popped = -Pop an element from the heap - x
          Subtract all the elements in the heap by y and pop if 0 or negative
          if the popped element is positive, push it to the heap              
    4.    Increment the result
}

Input:

examTime = [1000000000]*100000, a = 10000, b = 100

Answer 1

One optimisation is to convert the input of a and b, to a - b and b. This way you can reduce the max value with just a - b and then ... raise the lower threshold (which original is 0) with b instead of mutating all values.

Secondly, many heap implementations provide an exchange method, i.e. where the min-value is replaced with another value, after which the heap will restore the heap property. This requires fewer operations than a separate pop and push. The pop operation can still be used when no exchange should happen.

Finally, I see you are using a minheap and negate all values on it to mimic a maxheap. That is an implementation detail. I will assume we have a maxheap.

So:

func minOps(examTime, a, b) {
    threshold := 0
    diff := a - b
    maxheap := heapify(examTime)
    Loop while maxheap is not empty
          max := peek(maxheap)
          if max <= threshold: exit loop
          max := max - diff
          threshold := threshold + b
          if max > threshold: exchange(maxheap, max)
                        else: pop(maxheap)
    return threshold / b
}

Implementation in Python

from heapq import heapify, heappop, heapreplace

# Helper functions to use minheap implementation for a maxheap
def maxheapify(lst):
    for i, val in enumerate(lst):
        lst[i] = -val
    heapify(lst)

def maxheappeek(heap):
    return -heap[0]

def maxheapreplace(heap, val):
    heapreplace(heap, -val)

def minops(examTime, a, b):
    threshold = 0
    diff = a - b
    heap = examTime[:]
    maxheapify(heap)
    while heap:
        maxval = maxheappeek(heap)
        if maxval <= threshold:
            break
        maxval -= diff
        threshold += b
        if maxval > threshold:
            maxheapreplace(heap, maxval)
        else:
            heappop(heap)
    return threshold // b


result = minops([2, 3, 5], 3, 1)
print(result)  # 3