Welcome to Subscribe On Youtube
3219. Minimum Cost for Cutting Cake II
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
of sizem  1
, wherehorizontalCut[i]
represents the cost to cut along the horizontal linei
.verticalCut
of sizen  1
, whereverticalCut[j]
represents the cost to cut along the vertical linej
.
In one operation, you can choose any piece of cake that is not yet a 1 x 1
square and perform one of the following cuts:
 Cut along a horizontal line
i
at a cost ofhorizontalCut[i]
.  Cut along a vertical line
j
at a cost ofverticalCut[j]
.
After the cut, the piece of cake is divided into two distinct pieces.
The cost of a cut depends only on the initial cost of the line and does not change.
Return the minimum total cost to cut the entire cake into 1 x 1
pieces.
Example 1:
Input: m = 3, n = 2, horizontalCut = [1,3], verticalCut = [5]
Output: 13
Explanation:
 Perform a cut on the vertical line 0 with cost 5, current total cost is 5.
 Perform a cut on the horizontal line 0 on
3 x 1
subgrid with cost 1.  Perform a cut on the horizontal line 0 on
3 x 1
subgrid with cost 1.  Perform a cut on the horizontal line 1 on
2 x 1
subgrid with cost 3.  Perform a cut on the horizontal line 1 on
2 x 1
subgrid with cost 3.
The total cost is 5 + 1 + 1 + 3 + 3 = 13
.
Example 2:
Input: m = 2, n = 2, horizontalCut = [7], verticalCut = [4]
Output: 15
Explanation:
 Perform a cut on the horizontal line 0 with cost 7.
 Perform a cut on the vertical line 0 on
1 x 2
subgrid with cost 4.  Perform a cut on the vertical line 0 on
1 x 2
subgrid with cost 4.
The total cost is 7 + 4 + 4 = 15
.
Constraints:
1 <= m, n <= 10^{5}
horizontalCut.length == m  1
verticalCut.length == n  1
1 <= horizontalCut[i], verticalCut[i] <= 10^{3}
Solutions
Solution 1: Greedy + Two Pointers
For a given position, the earlier you cut, the fewer cuts are needed, so it is clear that positions with higher costs should be cut earlier.
Therefore, we can sort the arrays $\textit{horizontalCut}$ and $\textit{verticalCut}$ in descending order, and then use two pointers $i$ and $j$ to point to the costs in $\textit{horizontalCut}$ and $\textit{verticalCut}$, respectively. Each time, we choose the position with the larger cost to cut, while updating the corresponding number of rows and columns.
Each time a horizontal cut is made, if the number of columns before the cut was $v$, then the cost of this cut is $\textit{horizontalCut}[i] \times v$, and then the number of rows $h$ is incremented by one; similarly, each time a vertical cut is made, if the number of rows before the cut was $h$, then the cost of this cut is $\textit{verticalCut}[j] \times h$, and then the number of columns $v$ is incremented by one.
Finally, when both $i$ and $j$ reach the end, return the total cost.
The time complexity is $O(m \times \log m + n \times \log n)$, and the space complexity is $O(\log m + \log n)$. Here, $m$ and $n$ are the lengths of $\textit{horizontalCut}$ and $\textit{verticalCut}$, respectively.

class Solution { public long minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) { Arrays.sort(horizontalCut); Arrays.sort(verticalCut); long ans = 0; int i = m  2, j = n  2; int h = 1, v = 1; while (i >= 0  j >= 0) { if (j < 0  (i >= 0 && horizontalCut[i] > verticalCut[j])) { ans += 1L * horizontalCut[i] * v; ++h; } else { ans += 1L * verticalCut[j] * h; ++v; } } return ans; } }

class Solution { public: long long minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) { sort(horizontalCut.rbegin(), horizontalCut.rend()); sort(verticalCut.rbegin(), verticalCut.rend()); long long ans = 0; int i = 0, j = 0; int h = 1, v = 1; while (i < m  1  j < n  1) { if (j == n  1  (i < m  1 && horizontalCut[i] > verticalCut[j])) { ans += 1LL * horizontalCut[i++] * v; h++; } else { ans += 1LL * verticalCut[j++] * h; v++; } } return ans; } };

class Solution: def minimumCost( self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int] ) > int: horizontalCut.sort(reverse=True) verticalCut.sort(reverse=True) ans = i = j = 0 h = v = 1 while i < m  1 or j < n  1: if j == n  1 or (i < m  1 and horizontalCut[i] > verticalCut[j]): ans += horizontalCut[i] * v h, i = h + 1, i + 1 else: ans += verticalCut[j] * h v, j = v + 1, j + 1 return ans

func minimumCost(m int, n int, horizontalCut []int, verticalCut []int) (ans int64) { sort.Sort(sort.Reverse(sort.IntSlice(horizontalCut))) sort.Sort(sort.Reverse(sort.IntSlice(verticalCut))) i, j := 0, 0 h, v := 1, 1 for i < m1  j < n1 { if j == n1  (i < m1 && horizontalCut[i] > verticalCut[j]) { ans += int64(horizontalCut[i] * v) h++ i++ } else { ans += int64(verticalCut[j] * h) v++ j++ } } return }

function minimumCost(m: number, n: number, horizontalCut: number[], verticalCut: number[]): number { horizontalCut.sort((a, b) => b  a); verticalCut.sort((a, b) => b  a); let ans = 0; let [i, j] = [0, 0]; let [h, v] = [1, 1]; while (i < m  1  j < n  1) { if (j === n  1  (i < m  1 && horizontalCut[i] > verticalCut[j])) { ans += horizontalCut[i] * v; h++; i++; } else { ans += verticalCut[j] * h; v++; j++; } } return ans; }