I need some hints for proving the correctness/optimality of the below homework problem. It is a task-schedulding problem with deadlines and penalties. There are n tasks, each of which has a deadline and a penalty which incurs when the task is not scheduled or is scheduled to complete after the deadline. All tasks have the same length (1 hour) and may have the same deadline/penalty. The goal is to minimize the total penalties.
The algorithm:
Sort the tasks in the order of decreasing penalties. For task i = 1 to n Let d_i be its deadline, p_i be its penalty. Consider the first available time slot before d_i : # the goal is to schedule it as late as possible If it's empty: put task i there. move to next task. If it's occupied by task j: If p_j >= p_i : throw away task i. add p_i to the total penalty. If p_j < p_i : swap in task i. add p_j to the total penalty. Return the schedule and the total penalty.
I already have a hint but I still don't know where to start or what to do. The hint is to "start by considering an optimal solution and gradually transform it, preserving its optimality at each step, to the solution that the [above] algorithm produces". I just don't know what to do with an optimal solution. There may be >=1 of them and we can even assume that they result from other algorithms.
Thank you.