We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Cost for Cutting Cake I

Difficulty: Medium

Problem Description

There is an m x n cake that needs to be cut into 1 x 1 pieces. You are given integers m, n, and two arrays: horizontalCut and verticalCut. The goal is to return the minimum total cost to cut the entire cake into 1 x 1 pieces.

Key Insights

  • The cost of cutting is fixed and does not change after each cut.
  • Each horizontal cut affects all vertical pieces and vice versa.
  • To minimize the total cost, perform the most costly cuts last, as they will impact more pieces.
  • Sorting both cut arrays helps in efficiently determining the order of cuts.

Space and Time Complexity

Time Complexity: O(m log m + n log n) - due to sorting the cut arrays.
Space Complexity: O(1) - since we are using a constant amount of additional space.

Solution

The approach uses a greedy algorithm along with sorting. First, we sort both the horizontal and vertical cut costs in descending order. We then initialize two counters for the number of pieces created by horizontal and vertical cuts. As we iterate through the sorted cuts, we calculate the total cost based on the number of pieces affected by each cut. The total cost accumulates as we perform cuts.

Code Solutions

def minCost(m, n, horizontalCut, verticalCut):
    horizontalCut.sort(reverse=True)
    verticalCut.sort(reverse=True)
    
    total_cost = 0
    h_pieces = 1  # Initially, there's one horizontal piece
    v_pieces = 1  # Initially, there's one vertical piece
    
    h_index, v_index = 0, 0
    while h_index < len(horizontalCut) or v_index < len(verticalCut):
        if h_index < len(horizontalCut) and (v_index >= len(verticalCut) or horizontalCut[h_index] >= verticalCut[v_index]):
            total_cost += horizontalCut[h_index] * v_pieces
            h_pieces += 1
            h_index += 1
        else:
            total_cost += verticalCut[v_index] * h_pieces
            v_pieces += 1
            v_index += 1
            
    return total_cost
← Back to All Questions