Welcome to Subscribe On Youtube

3457. Eat Pizzas!

Description

You are given an integer array pizzas of size n, where pizzas[i] represents the weight of the ith pizza. Every day, you eat exactly 4 pizzas. Due to your incredible metabolism, when you eat pizzas of weights W, X, Y, and Z, where W <= X <= Y <= Z, you gain the weight of only 1 pizza!

• On odd-numbered days (1-indexed), you gain a weight of Z.
• On even-numbered days, you gain a weight of Y.

Find the maximum total weight you can gain by eating all pizzas optimally.

Note: It is guaranteed that n is a multiple of 4, and each pizza can be eaten only once.

 

Example 1:

Input: pizzas = [1,2,3,4,5,6,7,8]

Output: 14

Explanation:

• On day 1, you eat pizzas at indices [1, 2, 4, 7] = [2, 3, 5, 8]. You gain a weight of 8.
• On day 2, you eat pizzas at indices [0, 3, 5, 6] = [1, 4, 6, 7]. You gain a weight of 6.

The total weight gained after eating all the pizzas is 8 + 6 = 14.

Example 2:

Input: pizzas = [2,1,1,1,1,1,1,1]

Output: 3

Explanation:

• On day 1, you eat pizzas at indices [4, 5, 6, 0] = [1, 1, 1, 2]. You gain a weight of 2.
• On day 2, you eat pizzas at indices [1, 2, 3, 7] = [1, 1, 1, 1]. You gain a weight of 1.

The total weight gained after eating all the pizzas is 2 + 1 = 3.

 

Constraints:

• 4 <= n == pizzas.length <= 2 * 105
• 1 <= pizzas[i] <= 105
• n is a multiple of 4.

Solutions

Solution 1: Greedy + Sorting

According to the problem description, we can eat $4$ pizzas each day. On odd days, we get the maximum value among these $4$ pizzas, and on even days, we get the second largest value among these $4$ pizzas.

Therefore, we can sort the pizzas by weight in ascending order. We can eat for $\mathit{\text{days}}=n/4$ days, with $\mathit{\text{odd}}=(\mathit{\text{days}}+1)/2$ days being odd days and $\mathit{\text{even}}=\mathit{\text{days}}-\mathit{\text{odd}}$ days being even days.

For odd days, we can choose the largest $\mathit{\text{odd}}$ pizzas and the smallest $\mathit{\text{odd}}\times 3$ pizzas, with the increased weight being $\sum _{i=n-\mathit{\text{odd}}}^{n-1}\mathit{\text{pizzas}}[i]$.

For even days, among the remaining pizzas, we greedily choose the largest two pizzas and the smallest two pizzas each time, with the increased weight being $\sum _{i=n-\mathit{\text{odd}}-2}^{n-\mathit{\text{odd}}-2\times \mathit{\text{even}}}\mathit{\text{pizzas}}[i]$.

The time complexity is $O(n\times \log n)$, and the space complexity is $O(\log n)$. Here, $n$ is the length of the array $\mathit{\text{pizzas}}$.

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public long maxWeight(int[] pizzas) {
          int n = pizzas.length;
          int days = n / 4;
          Arrays.sort(pizzas);
          int odd = (days + 1) / 2;
          int even = days / 2;
          long ans = 0;
          for (int i = n - odd; i < n; ++i) {
              ans += pizzas[i];
          }
          for (int i = n - odd - 2; even > 0; --even) {
              ans += pizzas[i];
              i -= 2;
          }
          return ans;
      }
  }
  
  

• class Solution {
  public:
      long long maxWeight(vector<int>& pizzas) {
          int n = pizzas.size();
          int days = pizzas.size() / 4;
          ranges::sort(pizzas);
          int odd = (days + 1) / 2;
          int even = days - odd;
          long long ans = accumulate(pizzas.begin() + n - odd, pizzas.end(), 0LL);
          for (int i = n - odd - 2; even; --even) {
              ans += pizzas[i];
              i -= 2;
          }
          return ans;
      }
  };
  
  

• class Solution:
      def maxWeight(self, pizzas: List[int]) -> int:
          days = len(pizzas) // 4
          pizzas.sort()
          odd = (days + 1) // 2
          even = days - odd
          ans = sum(pizzas[-odd:])
          i = len(pizzas) - odd - 2
          for _ in range(even):
              ans += pizzas[i]
              i -= 2
          return ans
  
  

• func maxWeight(pizzas []int) (ans int64) {
  	n := len(pizzas)
  	days := n / 4
  	sort.Ints(pizzas)
  	odd := (days + 1) / 2
  	even := days - odd
  	for i := n - odd; i < n; i++ {
  		ans += int64(pizzas[i])
  	}
  	for i := n - odd - 2; even > 0; even-- {
  		ans += int64(pizzas[i])
  		i -= 2
  	}
  	return
  }
  
  

• function maxWeight(pizzas: number[]): number {
      const n = pizzas.length;
      const days = n >> 2;
      pizzas.sort((a, b) => a - b);
      const odd = (days + 1) >> 1;
      let even = days - odd;
      let ans = 0;
      for (let i = n - odd; i < n; ++i) {
          ans += pizzas[i];
      }
      for (let i = n - odd - 2; even; --even) {
          ans += pizzas[i];
          i -= 2;
      }
      return ans;
  }
  
  

All Problems

All Solutions