3218. Minimum Cost for Cutting Cake I

Hint

class Solution {
public:
    int minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut)
    {
        // Sorting the cuts in descending order to start from the largest piece

        // Counters for horizontal and vertical pieces
        // Variable to accumulate the minimum cost

        // Loop until we have processed all possible cuts
        while ()
        {
            // Compare the current largest horizontal cut with the current largest vertical cut
            if ()
            {
                // Add the cost of the horizontal cut multiplied by the number of vertical pieces + 1
            }
            else
            {
                // Add the cost of the vertical cut multiplied by the number of horizontal pieces + 1
            }
        }

        // If there are remaining horizontal cuts, add their costs
        while ()
        {

        }

        // If there are remaining vertical cuts, add their costs
        while ()
        {

        }

        // Return the accumulated minimum cost
    }
};

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

        int hPieces = 0, vPieces = 0;
        int minCost = 0;

        while (hPieces < m - 1 && vPieces < n - 1)
        {
            if (horizontalCut[hPieces] > verticalCut[vPieces])
            {
                minCost += horizontalCut[hPieces++] * (vPieces + 1);
            }
            else
            {
                minCost += verticalCut[vPieces++] * (hPieces + 1);
            }
        }

        while (hPieces < m - 1)
        {
            minCost += horizontalCut[hPieces++] * (vPieces + 1);
        }

        while (vPieces < n - 1)
        {
            minCost += verticalCut[vPieces++] * (hPieces + 1);
        }
        return minCost;
    }
};

• T: $O((m + n) \cdot \log (m + n))$
• S: $O(m + n)$