3219. Minimum Cost for Cutting Cake II

Intuition

The goal is to cut a cake into 1 × 1 pieces with the minimum cost. Each cut has a cost associated with it, and the cost is fixed regardless of the size of the piece being cut. The key to minimizing the total cost is to make the most expensive cuts first when they will affect the largest number of subsequent cuts. This approach leverages a greedy algorithm.

Approach: Greedy

Explanation:

1. Sort Cuts in Descending Order:
2. Sort the hCut and vCut arrays in descending order. This allows us to consider the most expensive cuts first.
3. Initialize Counters and Cost:
4. Use two counters: hCount to keep track of the number of horizontal segments and vCount for the number of vertical segments. Initialize both to 1.
5. Initialize i and j to 0 to traverse the hCut and vCut arrays respectively.
6. Initialize cost to accumulate the total cost of cuts.
7. Process Cuts in Descending Order:
8. Use a while loop to process both hCut and vCut arrays.
9. Compare the current highest cost from both arrays:
   • If the horizontal cut is more expensive, make this cut. The cost is added as hCut[i] * vCount, then increment i and hCount.
   • If the vertical cut is more expensive or equal, make this cut. The cost is added as vCut[j] * hCount, then increment j and vCount.
10. Process Remaining Cuts:
11. After the main loop, there may be remaining cuts in either hCut or vCut. Process these remaining cuts, multiplying by the current count of vertical or horizontal segments.
12. Return the Total Cost:
13. The accumulated cost represents the minimum total cost to cut the entire cake into (1 \times 1) pieces.

Complexity

• Time complexity: O((m + n) log (m + n)) due to sorting the cut arrays.
• Space complexity: O(1) as we are using a constant amount of extra space.

Code

class Solution {
public:
    int minimumCost(int m, int n, vector<int>& hCut, vector<int>& vCut) {
        sort(hCut.begin(), hCut.end(), greater());
        sort(vCut.begin(), vCut.end(), greater());

        int i = 0, j = 0;
        int hCount = 1, vCount = 1;
        int cost = 0;

        while (i < hCut.size() && j < vCut.size()) {
            if (hCut[i] > vCut[j]) {
                cost += hCut[i++] * vCount;
                ++hCount;
            }
            else {
                cost += vCut[j++] * hCount;
                ++vCount;
            }
        }

        while (i < hCut.size()) {
            cost += hCut[i++] * vCount;
        }

        while (j < vCut.size()) {
            cost += vCut[j++] * hCount;
        }

        return cost;
    }
};