cutting_boards.py

# source: https://www.hackerrank.com/challenges/board-cutting/problem
def boardCutting(cost_y, cost_x):
    MOD_INT = (10**9) + 7
    
    # sort each cost (asc)
    cost_y.sort() # O(nlogn)
    cost_x.sort() # O(mlogm)
    
    horizontal_boards = 1
    vertical_boards   = 1
    
    total_cost = 0
    cuts_left = len(cost_y) + len(cost_x)
    
    max_horizontal_cost = cost_y.pop()
    max_vertical_cost   = cost_x.pop()
    
    while cuts_left: # O(n+m)
        if max_horizontal_cost > max_vertical_cost: # make a horizontal cut
            # print(f"Making cut ({max_horizontal_cost} x {vertical_boards}) = {max_horizontal_cost * vertical_boards}")
            total_cost += max_horizontal_cost * vertical_boards
            horizontal_boards += 1
            # assign next max cost for consideration in next loop
            if cost_y:
                max_horizontal_cost = cost_y.pop()
            else:
                max_horizontal_cost = 0
        else: # make a vertical cut
            # print(f"Making cut ({max_vertical_cost} x {horizontal_boards}) = {max_vertical_cost * horizontal_boards}")
            total_cost += max_vertical_cost * horizontal_boards
            vertical_boards += 1
            # assign next max cost for consideration in next loop
            if cost_x:
                max_vertical_cost = cost_x.pop()
            else:
                max_vertical_cost = 0
        
        # mod to maintain low overhead
        total_cost = int(total_cost % MOD_INT)
        cuts_left -= 1
    
    # Total Time Comlexity = O(nlogn) + O(mlogm) + O(n+m) =>  O(nlogn + mlogm)
    return total_cost