finding and proving a greedy algorithm to maximize total energy 
Find a function $f:\mathbb{R}^2\to \mathbb{Z}$ that satisfies the following properties, or show that no such function exists:


*

*$f$ is increasing with respect to its first coordinate (i.e. $f(x, a) \leq f(y,a)$ for $x\leq y$)

*$f$ is decreasing with respect to its second coordinate (i.e. $f(a, x) \leq f(a,y)$ for $x\ge y$).

*$f$ can be used to solve the problem below as follows:

sort the $n$ pairs $(e[i], d[i])$ in decreasing order according to the value of $f$. When going through the new pairs in the sorted order, suppose you reach fruit $i$. Add $e[i]$ to the maximum if fruit $i$ is not yet expired.

Or find an alternative way to come up with a greedy algorithm to solve the problem below.


There are $n$ fruits, and each has an associated energy level, stored in the array e[1...n]. Also, each fruit has an expiry date, stored in the array d[1...n] (d[i] is the number of days from today fruit i expires). Both e[1...n] and d[1...n] only store positive values. A person wishes to maximize the total energy of the fruits they can take subject to the constraint that they take at most one fruit per day.


How would one design and prove a greedy algorithm for this problem?

I can't seem to find a correct greedy algorithm for this problem. I initially thought of repeatedly choosing the fruit with the highest ratio of energy to days until expiry, but there are counterexamples for this. For instance, consider the fruits satisfying $d = [3,1,2,4], e = [1,11,10,20]$. The greedy algorithm would choose fruits $2$ (ratio 11/1), 3 (ratio 10/1), 4 (ratio 20/1), giving an energy value of 41, which is smaller than the optimum of 42.

Also, I was wondering if there was an $o(n^2)$ greedy algorithm? If not, a dynamic programming algorithm running in $o(n^2)$ time is also fine.


Also, is it true that if any d[i] > n, then any optimal solution must select fruit $i$?

 A: I'm not sure we can use a greedy algorithm here, but dynamic programming should work, here is one in $\mathcal{O}(n^3)$n which is already better than maximum weight matching. First, sort the fruits following the $d$ values in increasing order, and sort the $e$ values in decreasing order when the fruits have the same $d$ value. It is easy to see that there is an optimal solution where the fruits are chosen in order in the sorted list.
Now, you can just do dynamic programming, with the following recurrence :
$p(k, i)$ is the optimal solution up to day $k$, where the last chosen fruit in the sorted list of fruits is $i$.
$p(k,i) = \max_{j < i} p(k-1, j) + e(i)$ if $d(i) \geq n$
$p(k,i) = 0$ else
A: A greedy algorithm At each stage do the following and repeat until no fruit or days remain unallocated.
Select the remaining fruit with maximum $e$-value. Allocate this fruit to the maximum possible day, $d$, such that $d$ has not yet been allocated and such that $d$ is not greater than the selected fruit's $d$-value.
If no such $d$ exists then delete the fruit from the list.
Otherwise this fruit is selected for day $d$ and both the fruit and the day are marked as being allocated.
Proof Suppose that from some stage there is a better solution than the one using the fruit $F$ on day $d$ given by the above algorithm.
This better solution cannot have a fruit allocated to $d$ with energy greater than $F$'s so simply replace such a fruit by $F$. In this manner we step through the stages, always being able to show that the above algorithm produces at least an equally good solution.
A: My algorithm is same as this answer but using Disjoint-set data structure.  In this solution, i am assuming that the range of dates is O(n). 
Let each date from minimum date to maximum expiry date (including both) be a set with single element date. The representative of these sets is always empty and can be used to place the fruit. Let us also create a sentinel set before the minimum date in which fruit cannot be placed.
Greedy solution

*

*At each stage, select the maximum energy fruit $i$. Find the representative of the set containing $d[i]$.

*If the representative is the sentinel, remove the fruit.

*If the representative is not a sentinel but the date $d'$, then place the fruit in the date $d'$ and combine the sets containing $d'$ and $d'-1$.

Extra
There is a mathematical structure called Weighted Matroid which has nice properties that helps us in solving greedy algorithms. This question can be reframed into a weighted matroid with independent set - set of fruits that follows the deadline constraint and weight - energy. For more details, you can look at the book "Introduction to Algorithms", chapter 16 Greedy algorithms, section Matroids.
Edit
To answer your second question

Also, is it true that if any d[i] > n, then any optimal solution must select fruit $i$?

Let $i$ be a fruit with $d[i] \ge n$. Let us assume that there exists an optimal configuration $C$ without fruit $i$. Hence $C$ has atmost $n-1$ fruits in it which implies $C$ has atmost $n-1$ fruits in the first $n$ days. So there exists an extra space within $d[i]$ where $i$ can be placed in $C$ and make it more optimal which is a contradiction since $C$ was assumed to be optimal. Hence any configuration must have fruit $i$ if $d[i] \ge n$.
Also, I don't have to assume that range of dates is O(n). The range of dates can be exactly $n$ because by the above statement, if $d[i]$ for any fruit $i$ is greater than $n$, we can set it back to $n$ and this won't change the solution space.
