Eat pizzas

Array Greedy Sorting

33.1% acceptance

Feb 25, 2026

107

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_weight(mut pizzas: Vec<i32>) -> i64 {
    pizzas.sort_unstable_by(|a,b| b.cmp(a)); // descending
    let n = pizzas.len();
    let days = n / 4;
    let odd_days = (days + 1) / 2;
    let even_days = days / 2;
    // On odd days: take the largest available (Z)
    // On even days: take the 2nd largest available (Y)
    // Greedy: sort descending. For odd days, pick top odd_days elements.
    // For even days, pick top even_days elements from the remaining after skipping every other.
    // Actually: each day uses 4 pizzas but gains only 1. Odd day gains Z (max of 4), even day gains Y (2nd max of 4).
    // Greedy: for odd days, always pick the largest available pizza as Z.
    // For even days, pick the 2nd largest available as Y.
    // Optimal: pick the top (odd_days) largest for odd days, then skip 1 and pick (even_days) for even days.
    let mut ans = 0i64;
    let mut idx = 0;
    for _ in 0..odd_days {
      ans += pizzas[idx] as i64;
      idx += 1;
    }
    idx += 1; // skip one (the "Y" that won't be gained on an odd day becomes unused)
    for _ in 0..even_days {
      ans += pizzas[idx] as i64;
      idx += 2; // skip one between each even-day pick
    }
    ans
  }
}