Eat Pizzas!

Problem 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.

Key Insights

• The total number of pizzas is guaranteed to be a multiple of 4.
• We need to maximize the weight gained based on the rules for odd and even days.
• Sorting the weights of the pizzas will allow us to efficiently determine the maximum weights for both odd and even days.
• The optimal strategy involves picking the heaviest available pizzas on each day.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the array of pizzas.
Space Complexity: O(1) - if we sort in place, otherwise O(n) if additional storage is used.

Solution

To solve the problem, we can follow these steps:

1. Sort the pizzas array in non-decreasing order.
2. Initialize variables to keep track of total weight gained.
3. Iterate through the pizzas, consuming the heaviest available ones each day:
   • For odd days, select the heaviest pizza and add its weight to the total.
   • For even days, select the second heaviest pizza and add its weight to the total.
4. Continue this until all pizzas are consumed.

This greedy approach ensures that we are maximizing the weight gain on each day by always selecting the heaviest pizzas available.

Code Solutions