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 II

Difficulty: Hard

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, which represent the costs to cut along horizontal and vertical lines respectively. The goal is to return the minimum total cost to cut the entire cake into 1 x 1 pieces.

Key Insights

  • Each cut increases the number of pieces, which multiplies the cost of subsequent cuts.
  • The order of cuts affects the total cost, making it important to prioritize cuts based on their costs.
  • Using a max-heap (or a sorted approach) can help efficiently manage and select the largest costs to maximize the multipliers for the cuts.

Space and Time Complexity

Time Complexity: O((m + n) log(m + n))
Space Complexity: O(m + n)

Solution

To solve this problem, we can utilize a greedy approach combined with sorting. First, sort the horizontalCut and verticalCut arrays in descending order. We then use two pointers to traverse these arrays, simulating the cutting process. Each time we make a cut, we take the cost of the cut and multiply it by the number of pieces affected by that cut (which is determined by the number of previous cuts). This continues until all cuts are made.

  1. Sort both horizontalCut and verticalCut in descending order.
  2. Initialize counters for the number of horizontal and vertical pieces.
  3. Use two pointers to iterate through the sorted cuts, adding to the total cost based on the current cut and the number of pieces affected.
  4. Return the total cost.

Code Solutions

def minCost(m, n, horizontalCut, verticalCut):
    horizontalCut.sort(reverse=True)
    verticalCut.sort(reverse=True)

    total_cost = 0
    h_count = 1  # Initial pieces created by horizontal cuts
    v_count = 1  # Initial pieces created by vertical cuts

    h, v = 0, 0

    while h < len(horizontalCut) and v < len(verticalCut):
        if horizontalCut[h] >= verticalCut[v]:
            total_cost += horizontalCut[h] * v_count
            h_count += 1
            h += 1
        else:
            total_cost += verticalCut[v] * h_count
            v_count += 1
            v += 1

    while h < len(horizontalCut):
        total_cost += horizontalCut[h] * v_count
        h += 1

    while v < len(verticalCut):
        total_cost += verticalCut[v] * h_count
        v += 1

    return total_cost
← Back to All Questions