Minimum Cost for Cutting Cake II

Problem Description

So, you want to cut a cake, huh? But wait, it’s not just any cake; it’s a cake that costs you money every time you slice it! Welcome to the world of Minimum Cost for Cutting Cake II. Imagine you’re at a birthday party, and instead of just slicing the cake and serving it, you have to pay for every cut you make. Sounds like a party, right?

In this problem, you are given a rectangular cake of size m x n, and you have to make horizontal and vertical cuts. Each cut has a cost associated with it, and your goal is to minimize the total cost of cutting the cake. It’s like trying to save money while planning a party—good luck with that!

Code Solution


class Solution:
    def minimumCost(
        self,
        m: int,
        n: int,
        horizontalCut: list[int],
        verticalCut: list[int],
    ) -> int:
        ans = 0
        sumH = sum(horizontalCut)
        sumV = sum(verticalCut)

        horizontalCut.sort()
        verticalCut.sort()

        while horizontalCut and verticalCut:
            if horizontalCut[-1] > verticalCut[-1]:
                ans += horizontalCut[-1] + sumV
                sumH -= horizontalCut.pop()
            else:
                ans += verticalCut[-1] + sumH
                sumV -= verticalCut.pop()

        return ans + sumH + sumV

Approach

The approach taken in the provided code is quite clever. It sorts the horizontal and vertical cuts in descending order and then iteratively chooses the most expensive cut to make. By always opting for the largest cut available, it ensures that the total cost is minimized. The algorithm keeps track of the remaining sums of horizontal and vertical cuts, adding them to the total cost as cuts are made.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O((m + n) log(m + n))
Space Complexity	O(1)

Real-World Example

Let’s say you’re at a bakery, and you want to buy a cake for a party. The baker tells you that every time you want a slice, it costs you a dollar. If you want to cut it into smaller pieces, you’ll have to pay for each cut. So, you decide to make the biggest cuts first to minimize your costs. This is exactly what the algorithm does—prioritizing the most expensive cuts to save money in the long run.