half_consumption_custom_priority_queue.py.py

def add_fans(ranked_machines, total_initial_consumption, total_current_consumption, n_fans):

    # Resolve the recursion, because we have reached the target: "just below half of initial consumption"
    if total_current_consumption <= total_initial_consumption / 2:
        return n_fans


    # Compute the site that have the largest amount of consumption and the 
    # total amount of consumption for the company
    worse_machine = ranked_machines[0] # "Extracting" from the heap

    total_current_consumption = total_current_consumption - worse_machine / 2 # Update current total consumption
    ranked_machines[0] = worse_machine / 2 # Computing new worst machine consumption after fan
    heapify(ranked_machines, len(ranked_machines), 0) # Rebuild the heap since element 0 was halved and is probably no longer the max


    # Recurse, and place a fan on the new worse factory
    return add_fans(ranked_machines, total_initial_consumption, total_current_consumption, n_fans + 1)
  
  
def create_heap(elements_list):
    # Pretty similar to heapsort - It's just its first part
    i = (len(elements_list) / 2)
    while(i > 0):
        i -= 1
        heapify(elements_list, len(elements_list), i)
        

def solution(A):
    # write your code in Python 3.6

    # This is a greedy algorithm, that will try to put fans first on those machines
    # that have the largest contribution to the overall company consumption
    company_consumption = sum(A)
    ranked_machines = list(A) # Make a copy of the incoming array
    create_heap(ranked_machines) # Build the heap

    return add_fans(ranked_machines, company_consumption, company_consumption, 0)