So I just started learning greedy algorithms and I have a problem that I want to solve. The statement is as follows:
In your calendar you have an $L$ list of all the tasks you need to complete today. For each task $i \in L$ the duration $d_i \in \mathbb{N}$ is specified which indicates the time required to complete it and a penalty factor $p_i \in \mathbb{Z^+}$ which aggravates the delay. You must determine in what order to perform all the tasks to get the result that accumulates less total penalty.
Note that:
• In an instant you can only perform one task,
• Once you start a task, you must continue it until it is completed, and
• All tasks must be completed.
The actual penalty associated with a task $i \in L$ is the completion time $t_i$ of its completion, multiplied by its penalty $p_i$. The completion time $t_i$ corresponds to the time elapsed from the start of the working day (i.e. from time instant 0) to the time the task has been completed.
Provide an algorithm (as efficient as you can) to solve it.
I have figured out that the completion of a task $i ∈ L$ with completion time $t_i$ must started at instant $t_i - d_i$.
I'm stuck with the optimization criteria. I tried sorting the tasks by $p_i$ decreasingly, or by $p_i * d_i$ increasingly and doing the tasks in such order, but it doesn't work. I can find a counter-example for both approaches. What would be a good optimization criteria for this problem?