Consider a situation in which we have a single resource and a set of n tasks to use the resource for an interval of time. Assume that the resource is available starting at time \(0\). Every task i has a deadline \(d_i\) , and \(i_t\) requires a contiguous time interval of length \(t_i\), but it is willing to be scheduled at any time before the deadline. Each accepted task must be assigned an interval of time of length \(t_i\), and different requests must be assigned non overlapping intervals.
In this exercise you have to plan all tasks. It is allowed to schedule a task with a delay. The algorithm has to determine the start time and end time \(i\). The end time of a task \(i\) is \(f(i) = s(i) + t_i\). We call a task delayed if the task’s end time is after it’s deadline: \(f(i) > d_i\). The end time of a task \(i\) is $f(i) = s(i) + t_i$
Your tasks is to design and implement an algorithm that schedules the tasks in an non overlapping way such that \(L = max_i l_i\) is minimal.
Write a Python-function schedule(tasks: list) that takes a list of tasks as it’s argument.
A task is represented as a tuple tuple(task label, length, deadline).
The function schedule should return a list of tuples tuple(task label, start execution time, end execution time) in order of execution.
>>> schedule([('a', 1, 7), ('b', 2, 5), ('c', 3, 5), ('d', 4, 6)])
[('b', 0, 2), ('c', 2, 5), ('d', 5, 9), ('a', 9, 10)]
>>> schedule([])
[]