An answer to this question on Stack Overflow.

Question

I am stuck regarding the following question. Do you have an idea? Of course, brute-forcing all permutations solves the problem. However, is there another approach?

Suppose you sell apples and each apple has an associated "time to rot" until it cannot be sold anymore.

Suppose also that all apples have a separate price dependent on their aesthetics. The price is constant until the apple has rotten, then it becomes zero.

Selling an apple takes some constant time, therefore you cannot sell them all but only the first k apples.

In which order should you sell your slowly rotting apples in order to maximize your outcome?

Do you have any hints which type of literature could help here? Like operations research or queueing theory?

Answer

Assuming that time is discrete and that you can only sell one apple per time unit, I think the following algorithm would do the trick.

Sort the apples in order of decreasing value. Now, label the apples [1,N].

Let the apples rot in time R1, R2, R3, ...

Let the apples have value V1, V2, V3, ...

Construct an array S1, S2, S3, .... This is the order in which you will sell each apple.

Take the most expensive apple. Sell this apple at time R1. If you sell the apple at any later point, it will have no value. If you sell the apple at any earlier point, you may be selling it at a time when you could have sold a different apple and selling both apples has more value than selling only one apple.

Consider the apple with the second highest value. If R2 is not R1, then sell the apple at time R2. If R2 is equal to R1, then sell this apple at time R2-1. This way, we are still selling the apple as late as possible to keep our options open, but still prioritizing the apples by value (V2 over V3, and V1 over V2).

Perform the above for all of the apples. If there is no time slot in which to sell an apple, that means only more valuable apples are being sold during that time, which is the better choice.

In pseudocode:

Object Apple:
  V - Value of Apple
  R - Rot time
Let Apples[N] be an array of type Apple
Let S[N] be an integer array initialized to -1
Sort Apples in order of decreasing V.
Foreach i in [0,N):
  for j=Apples[i].R to 0 by -1
    if S[j]==-1:
      S[j]=i
      break