Given a list of \(n\) tasks, all tasks have the same time. Suppose every task takes 1 unit of time. Every task is given a deadline and a penaltiy, that has to be paid when the task is not executed. Design a greedy algorithm that schedules the tasks in such a way that the total penality is minimised.
Implement a function plan(tasks: list). This function takes a list of tasks as its input and returns the list of tasks that should be executed, without missing the deadlines.
The tasks placed on position \(i\) in the returned list, will be executed on time stamp \(i\). The result list contains only the tasks that can be executed before it’s deadline. (The resulting list can also contain Nones if there is no task that can be executed on those timestamps.)
A task is represented as a tuple tuple(deadline, penalty).
>>> plan([(4, 5), (10, 6), (3, 4), (5, 10), (4, 8), (5, 13), (2, 4), (7, 17), (5, 12), (3, 9)])
[(4, 8), (3, 9), (5, 10), (5, 12), (5, 13), None, (7, 17), None, None, (10, 6)]
>>> plan([(1, 4), (1, 8), (1, 3), (1, 12), (1, 7)])
[(1, 12)]
>>> plan([(4, 5), (10, 6), (3, 4), (5, 10), (4, 8), (8, 13), (2, 4), (7, 17), (7, 12), (10, 9)])
[(2, 4), (3, 4), (4, 5), (4, 8), (5, 10), (7, 12), (7, 17), (8, 13), (10, 6), (10, 9)]