Eat Pizzas!

Problem Description

You are given an integer array pizzas of length n (a multiple of 4) where pizzas[i] represents the weight of the iᵗʰ pizza. Every day you must eat exactly 4 pizzas. However, on an odd‐numbered day (1-indexed) you gain weight equal to the heaviest pizza in that set, while on an even-numbered day you gain weight equal to the second heaviest pizza in the set. You can partition and order the pizzas arbitrarily into days. Return the maximum total weight you can gain by eating all the pizzas optimally.

Key Insights

• Since every day you consume exactly 4 pizzas and only one pizza’s weight (either the largest or second largest) in that group will contribute, the grouping strategy is crucial.
• You are allowed to rearrange pizzas arbitrarily into groups and pick which groups are assigned to odd days (gain the maximum) and which to even days (gain the second maximum).
• The optimal grouping turns out to “pair” high‐value pizzas with low–value ones so that two relatively high pizzas appear in one group. Then, by smartly assigning days, you can take advantage of the high “maximum” on odd days and a moderately high “second maximum” on even days.
• A key observation is that if you sort the pizzas in ascending order, the answer can be derived by summing every second pizza (from the end) for exactly n/4 groups. For example, with pizzas sorted, the optimal contribution uses the pizzas at indices n–1, n–3, n–5, … (for n/4 terms).

Space and Time Complexity

Time Complexity: O(n log n) (due to sorting the array)
Space Complexity: O(n) (depending on the sorting implementation; additional space is O(1) apart from the sorted array)

Solution

The idea is to first sort the array of pizza weights in ascending order. Once sorted, the maximum overall gain can be realized by “grouping” the pizzas optimally into n/4 groups such that each group has two high‐weight pizzas. After sorting, one can prove that the optimal sum equals the sum of the pizzas at indices n–1, n–3, n–5, ... until n/4 pizzas have been chosen.
Here is the reasoning:

1. Sorting makes it easier to pick the largest available pizzas.
2. In any valid grouping of 4 pizzas, you would like to “spend” as little as possible on the pizzas whose weights are wasted (the ones that do not contribute) while “saving” two high weights for deciding the day’s gain.
3. By pairing one of the two highest remaining pizzas with three of the smallest available pizzas, you guarantee that when it is scheduled on an odd day, you contribute with the highest pizza; when scheduled on an even day (if forced), you contribute with the second highest which is still as high as possible given the remaining choices.
4. With complete freedom to reorder days, you can always assign the groups so that the sum of the gained weights is maximized. This turns out to be equivalent to summing the pizzas at positions n–1, n–3, … for exactly n/4 terms.

Code Solutions