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

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

Intuition

To solve the problem, the main objective is to maximize the gain of weight from eating the pizzas over several days, where we eat exactly 4 pizzas per day. The approach revolves around sorting and optimizing the choice of pizzas for odd and even days.

Approach

Sorting the Array: By sorting the array of pizzas by weight in ascending order, we ensure easy access to the largest pizzas when needed for maximum weight gain on odd days, and the second-largest on even days.
Calculate the Number of Days: Given that n is a multiple of 4, we calculate the number of days as days = n / 4.
Divide Odd and Even Days:
- The odd days are calculated as (days + 1) // 2.
- The even days are the remaining days after accounting for the odd days.
Weight Gain on Odd Days:
- On odd days, we focus on maximizing the pizza weight by selecting the largest available pizzas. The weight gained is the sum of the largest odd pizzas.
Weight Gain on Even Days:
- On even days, we choose pizzas such that the second-largest weight among the chosen four pizzas contributes to the weight gain. This selection is greedily made from the remaining pizzas after accounting for those eaten on odd days.

By systematically selecting the largest pizzas for odd days and the optimal pizzas for even days, we can achieve the maximum possible weight gain over the entire period.

Learn more about Greedy and Sorting patterns.

Solution Approach

To implement the solution, we use a combination of sorting and a greedy approach to maximize the weight gain according to the problem's conditions. Here's a detailed breakdown of the steps involved:

Sorting the Pizzas: Begin by sorting the pizzas array in ascending order. This makes it efficient to access the largest or specific-ranked pizzas required for each day's calculation.
Determining Days: Calculate the total number of days as days = len(pizzas) // 4. Given that n is guaranteed to be a multiple of 4, this division precisely determines the number of complete days.
Splitting into Odd and Even Days:
- Calculate how many of these days are odd using odd = (days + 1) // 2.
- The remaining days are even, calculated as even = days - odd.
Weight Gain Calculation:
- For odd days, select the largest odd pizzas. This is done by taking the sum of the top odd elements from the end of the sorted pizzas list: sum(pizzas[-odd:]).
- For even days, choose the required pizzas such that the second-largest pizza weight contributes to the gain for each of these days. This involves a loop adjusting the index to always select the second-largest of a sequence of four. The contribution to weight from even days is incorporated by further iterating:
```
i = len(pizzas) - odd - 2
for _ in range(even):
    ans += pizzas[i]
    i -= 2
```
Returning the Result:
- The total weight gain is accumulated in the variable ans, which is initialized with the weight gain from odd days and incremented within the loop for even days. Finally, return ans as the maximum possible weight gain.

This approach leverages the sorted order of pizzas, ensuring that the largest possible weights contribute to the gain while adhering to the specific conditions for odd and even days.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to apply the solution approach:

Given Example:

Suppose we have an array of pizzas with the following weights: pizzas = [3, 6, 9, 12, 15, 18, 21, 24]. This example involves 8 pizzas, meaning we will eat over 2 complete days (8/4 = 2 days).

Step 1: Sort the Array

Start by sorting the array of pizzas by weight, which is already sorted in this case: [3, 6, 9, 12, 15, 18, 21, 24].

Step 2: Determine Number of Days

Calculate total days: days = 8 / 4 = 2.

Step 3: Odd and Even Days Calculation

Determine odd days: (2 + 1) // 2 = 1 (1 odd day).
Determine even days: 2 - 1 = 1 (1 even day).

Step 4: Weight Gain Calculation

Weight Gain on Odd Day:
- Select the heaviest pizza from the last 1 pizza after sorting for the odd day: pizzas[-1] = 24.
- Total gain on odd days: 24.
Weight Gain on Even Day:
- Select the second largest pizza among the first 4 for even day which is the 2nd largest from the top positions: pizzas[-3] = 21.
- Total gain on even days: 21.

Step 5: Return Result

Total weight gain by adding gains from both days: 24 (odd day) + 21 (even day) = 45.

Hence, the maximum total weight gain is 45 by eating all the pizzas optimally.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maxWeight(self, pizzas: List[int]) -> int:
5        # Calculate the number of days
6        days = len(pizzas) // 4
7      
8        # Sort the pizza weights in ascending order
9        pizzas.sort()
10      
11        # Calculate the number of days allocated for odd positions
12        odd = (days + 1) // 2
13      
14        # Calculate the number of days allocated for even positions
15        even = days - odd
16      
17        # Initialize the maximum weight with the sum of heaviest pizzas for odd days
18        max_weight = sum(pizzas[-odd:])
19      
20        # Start from the correct position for even days
21        i = len(pizzas) - odd - 2
22      
23        # Iterate to pick pizzas for even days
24        for _ in range(even):
25            # Add the weight of the current pizza to the max_weight
26            max_weight += pizzas[i]
27            # Move two steps left to pick the next pizza for even days
28            i -= 2
29      
30        # Return the final maximum weight
31        return max_weight
32

1import java.util.Arrays;
2
3class Solution {
4    public long maxWeight(int[] pizzas) {
5        int n = pizzas.length; //Total number of pizzas
6        int days = n / 4; //Total days over which pizzas are distributed
7        Arrays.sort(pizzas); //Sort the pizzas array to organize weights in ascending order
8        int oddDays = (days + 1) / 2; //Calculate number of odd days (where we pick based on odd indices)
9        int evenDays = days / 2; //Calculate number of even days
10      
11        long maximumWeight = 0; //Initialize variable to accumulate maximum weight
12      
13        // Add the largest weights from odd days to maximumWeight
14        for (int i = n - oddDays; i < n; ++i) {
15            maximumWeight += pizzas[i];
16        }
17      
18        // Add the necessary weights from even days to maximumWeight
19        for (int i = n - oddDays - 2; evenDays > 0; --evenDays) {
20            maximumWeight += pizzas[i];
21            i -= 2; //Skip to the next necessary position for even days
22        }
23      
24        return maximumWeight; //Return the calculated maximum weight
25    }
26}
27

1#include <vector>
2#include <algorithm>
3#include <numeric>
4#include <ranges>
5
6class Solution {
7public:
8    // Function to calculate maximum weight of pizzas a restaurant can take
9    long long maxWeight(std::vector<int>& pizzas) {
10        int n = pizzas.size();  // Get number of pizzas
11        int days = n / 4;  // Calculate how many days the restaurant operates
12
13        // Sort pizzas in non-decreasing order
14        std::ranges::sort(pizzas);
15
16        int odd = (days + 1) / 2;  // Calculate odd day count
17        int even = days - odd;  // Calculate even day count
18
19        // Start with the sum of the largest 'odd' number of pizzas 
20        long long ans = std::accumulate(pizzas.begin() + n - odd, pizzas.end(), 0LL);
21
22        // Add largest 'even' number of pizzas from remaining ones in every two steps
23        for (int i = n - odd - 2; even; --even) {
24            ans += pizzas[i];
25            i -= 2;  // Move two steps backwards
26        }
27
28        return ans;  // Return the total maximum weight
29    }
30};
31

1function maxWeight(pizzas: number[]): number {
2    const n = pizzas.length; // Number of pizzas available
3    const days = n >> 2; // Calculate days as floor(n / 4)
4
5    // Sort the array in ascending order
6    pizzas.sort((a, b) => a - b);
7
8    // Calculate odd and even counts for the distribution scheme
9    const odd = (days + 1) >> 1; // Calculate odd number of days (half of days rounded up)
10    let even = days - odd; // Calculate even number of days
11
12    let totalWeight = 0; // Initialize the total weight counter
13
14    // Sum the largest 'odd' number of pizzas
15    for (let i = n - odd; i < n; ++i) {
16        totalWeight += pizzas[i];
17    }
18
19    // Sum the weights for the even days from the second-largest
20    for (let i = n - odd - 2; even > 0; --even) {
21        totalWeight += pizzas[i];
22        i -= 2; // Move two indices back for each even day
23    }
24
25    return totalWeight; // Return the total maximum weight
26}
27

Time and Space Complexity

The time complexity of the code is O(n \log n) due to the sorting operation on the pizzas list, where n is the length of the list. The subsequent operations, such as calculating odd and even and the loop for summing the selected elements, are O(n).

The space complexity is O(\log n), which is needed for the sorting operation if using a recursive algorithm like Timsort, typically used by Python's sort function, which requires additional space for the recursion stack.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: