0
$\begingroup$

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?

Improve this question
$\endgroup$
9
  • $\begingroup$ Where did you encountered this task? Please credit the original source of all copied material. See cs.stackexchange.com/help/referencing. $\endgroup$
    – D.W. ♦
    Oct 26 '20 at 16:10
  • $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$
    – D.W. ♦
    Oct 26 '20 at 16:13
  • $\begingroup$ @D.W. This problem is from a list of problems of my university. I translated the problem statement to english to post it. I'm stuck with the optimization criteria. I've tried sorting the tasks by penalty factor decreasingly, or sorting by $d_i * p_i$ increasingly, but it doesn't work. I can find counter-examples for both approaches. $\endgroup$
    – cs_learner
    Oct 26 '20 at 18:24
  • $\begingroup$ In my opinion you should still credit the original source, even when translating. Usually there are only a handful of plausible optimization criteria, e.g., $p_i$ or $p_i d_i$ or $p_i/d_i$ etc., so the typical approach to greedy algorithms is to try each of them and see if you can find a counterexample. Are you sure that there is a greedy algorithm? $\endgroup$
    – D.W. ♦
    Oct 26 '20 at 19:21
  • $\begingroup$ Original source, exercise number 46: cs.upc.edu/~mjserna/docencia/grauA/T20/llista2.pdf. There must be a greedy algorithm. In the original statement it states to solve it using a greedy algorithm. $\endgroup$
    – cs_learner
    Oct 26 '20 at 19:55
1
$\begingroup$

Note the minimum penalty for a task is always $p_i d_i$. If I choose at a point in time to do task $i$, then all other tasks $j$ will incur an extra penalty of $p_j d_i$.

Therefore, you need to do the most expensive task first (i.e., having the largest $p_i$). If there are multiple such tasks, then the one with the shortest $d_i$ needs to be performed first.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.