Skip to content

3218. Minimum Cost for Cutting Cake I 👍

  • Time: $O(\texttt{sort}(\texttt{horizontalCut}) + \texttt{sort}(\texttt{verticalCut}))$
  • Space: $O(\texttt{sort}(\texttt{horizontalCut}) + \texttt{sort}(\texttt{verticalCut}))$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  int minimumCost(int m, int n, vector<int>& horizontalCut,
                  vector<int>& verticalCut) {
    int cost = 0;
    int sumH = accumulate(horizontalCut.begin(), horizontalCut.end(), 0);
    int sumV = accumulate(verticalCut.begin(), verticalCut.end(), 0);

    ranges::sort(horizontalCut, greater<>());
    ranges::sort(verticalCut, greater<>());

    for (int i = 0, j = 0; i < m - 1 && j < n - 1;)
      if (horizontalCut[i] > verticalCut[j]) {
        cost += horizontalCut[i] + sumV;
        sumH -= horizontalCut[i++];
      } else {
        cost += verticalCut[j] + sumH;
        sumV -= verticalCut[j++];
      }

    return cost + sumH + sumV;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public int minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {
    int cost = 0;
    int sumH = Arrays.stream(horizontalCut).sum();
    int sumV = Arrays.stream(verticalCut).sum();

    Arrays.sort(horizontalCut);
    Arrays.sort(verticalCut);

    for (int i = m - 2, j = n - 2; i >= 0 && j >= 0;)
      if (horizontalCut[i] > verticalCut[j]) {
        cost += horizontalCut[i] + sumV;
        sumH -= horizontalCut[i--];
      } else {
        cost += verticalCut[j] + sumH;
        sumV -= verticalCut[j--];
      }

    return cost + sumH + sumV;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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