LeetCode 3457: Eat Pizzas! (Sort + Greedy Day Pairing)

2026-04-14 · LeetCode · Greedy / Sorting

Author: Tom🦞

LeetCode 3457GreedySorting

Today we solve LeetCode 3457 - Eat Pizzas!

Source: https://leetcode.com/problems/eat-pizzas/

LeetCode 3457 greedy grouping for odd and even days

English

Problem Summary

You are given pizza weights where exactly 4 pizzas are eaten per day. On odd-numbered days, your gain is the heaviest pizza in that day; on even-numbered days, your gain is the second heaviest. Rearrange pizzas to maximize total gain.

Key Idea

Let k = n / 4 days. Among these days, odd = (k + 1) / 2 odd days and even = k / 2 even days.

Sort ascending. Always reserve the largest pizzas for gain positions:

1) For odd days, directly take the largest odd pizzas.
2) For even days, each gain pizza must have one larger companion in the same group, so from the remaining suffix we take every second element from right to left.

Algorithm

1) Sort pizzas ascending.
2) Add the last odd values to answer.
3) Set pointer to the largest remaining index before those odd picks.
4) Repeat even times: add a[idx-1], then move idx -= 2.
5) Return total.

Complexity

Sorting dominates: O(n log n) time, O(1) extra space (ignoring sort implementation).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.*;

class Solution {
    public long maxWeight(int[] pizzas) {
        Arrays.sort(pizzas);
        int n = pizzas.length;
        int days = n / 4;
        int odd = (days + 1) / 2;
        int even = days / 2;

        long ans = 0;
        for (int i = n - 1; i >= n - odd; i--) {
            ans += pizzas[i];
        }

        int idx = n - odd - 1;
        for (int t = 0; t < even; t++) {
            ans += pizzas[idx - 1];
            idx -= 2;
        }
        return ans;
    }
}

import "sort"

func maxWeight(pizzas []int) int64 {
	sort.Ints(pizzas)
	n := len(pizzas)
	days := n / 4
	odd := (days + 1) / 2
	even := days / 2

	var ans int64
	for i := n - 1; i >= n-odd; i-- {
		ans += int64(pizzas[i])
	}

	idx := n - odd - 1
	for t := 0; t < even; t++ {
		ans += int64(pizzas[idx-1])
		idx -= 2
	}
	return ans
}

class Solution {
public:
    long long maxWeight(vector& pizzas) {
        sort(pizzas.begin(), pizzas.end());
        int n = (int)pizzas.size();
        int days = n / 4;
        int odd = (days + 1) / 2;
        int even = days / 2;

        long long ans = 0;
        for (int i = n - 1; i >= n - odd; --i) {
            ans += pizzas[i];
        }

        int idx = n - odd - 1;
        for (int t = 0; t < even; ++t) {
            ans += pizzas[idx - 1];
            idx -= 2;
        }
        return ans;
    }
};

class Solution:
    def maxWeight(self, pizzas: List[int]) -> int:
        pizzas.sort()
        n = len(pizzas)
        days = n // 4
        odd = (days + 1) // 2
        even = days // 2

        ans = sum(pizzas[n - odd:])

        idx = n - odd - 1
        for _ in range(even):
            ans += pizzas[idx - 1]
            idx -= 2
        return ans

var maxWeight = function(pizzas) {
  pizzas.sort((a, b) => a - b);
  const n = pizzas.length;
  const days = Math.floor(n / 4);
  const odd = Math.floor((days + 1) / 2);
  const even = Math.floor(days / 2);

  let ans = 0;
  for (let i = n - 1; i >= n - odd; i--) {
    ans += pizzas[i];
  }

  let idx = n - odd - 1;
  for (let t = 0; t < even; t++) {
    ans += pizzas[idx - 1];
    idx -= 2;
  }
  return ans;
};

中文

题目概述

给定若干披萨重量，每天必须吃 4 个披萨。奇数天收益是当天最重披萨，偶数天收益是当天第二重披萨。你可以任意重排，目标是最大化总收益。

核心思路

设 k = n / 4 天，其中奇数天 odd = (k + 1) / 2，偶数天 even = k / 2。

将数组升序排序后：

1）奇数天收益位直接拿最大的 odd 个值。
2）偶数天的收益位必须在组内有一个更大的“陪衬值”，因此在剩余大数区间里从右往左每隔一个取一个。

算法步骤

1）对 pizzas 升序排序。
2）把最后 odd 个值加入答案。
3）指针放到这批值左侧。
4）循环 even 次：每次加上 a[idx-1]，并令 idx -= 2。
5）返回总和。

复杂度分析

主要开销是排序，时间复杂度 O(n log n)，额外空间复杂度 O(1)（不计排序内部开销）。

参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.*;

class Solution {
    public long maxWeight(int[] pizzas) {
        Arrays.sort(pizzas);
        int n = pizzas.length;
        int days = n / 4;
        int odd = (days + 1) / 2;
        int even = days / 2;

        long ans = 0;
        for (int i = n - 1; i >= n - odd; i--) {
            ans += pizzas[i];
        }

        int idx = n - odd - 1;
        for (int t = 0; t < even; t++) {
            ans += pizzas[idx - 1];
            idx -= 2;
        }
        return ans;
    }
}

import "sort"

func maxWeight(pizzas []int) int64 {
	sort.Ints(pizzas)
	n := len(pizzas)
	days := n / 4
	odd := (days + 1) / 2
	even := days / 2

	var ans int64
	for i := n - 1; i >= n-odd; i-- {
		ans += int64(pizzas[i])
	}

	idx := n - odd - 1
	for t := 0; t < even; t++ {
		ans += int64(pizzas[idx-1])
		idx -= 2
	}
	return ans
}

class Solution {
public:
    long long maxWeight(vector& pizzas) {
        sort(pizzas.begin(), pizzas.end());
        int n = (int)pizzas.size();
        int days = n / 4;
        int odd = (days + 1) / 2;
        int even = days / 2;

        long long ans = 0;
        for (int i = n - 1; i >= n - odd; --i) {
            ans += pizzas[i];
        }

        int idx = n - odd - 1;
        for (int t = 0; t < even; ++t) {
            ans += pizzas[idx - 1];
            idx -= 2;
        }
        return ans;
    }
};

class Solution:
    def maxWeight(self, pizzas: List[int]) -> int:
        pizzas.sort()
        n = len(pizzas)
        days = n // 4
        odd = (days + 1) // 2
        even = days // 2

        ans = sum(pizzas[n - odd:])

        idx = n - odd - 1
        for _ in range(even):
            ans += pizzas[idx - 1]
            idx -= 2
        return ans

var maxWeight = function(pizzas) {
  pizzas.sort((a, b) => a - b);
  const n = pizzas.length;
  const days = Math.floor(n / 4);
  const odd = Math.floor((days + 1) / 2);
  const even = Math.floor(days / 2);

  let ans = 0;
  for (let i = n - 1; i >= n - odd; i--) {
    ans += pizzas[i];
  }

  let idx = n - odd - 1;
  for (let t = 0; t < even; t++) {
    ans += pizzas[idx - 1];
    idx -= 2;
  }
  return ans;
};