'How to implement interval scheduling algorithm
I am asked to:
Angusina is attending the Christchurch Buskers Festival and wants to see as many shows as she can on a given day. She has a list of all the shows in an arbitrary order. Each one is a tuple with a title, a start time (conveniently specified in minutes from midnight) and a duration, also in minutes. Help Angusina decide what shows to attend.
Write a function print_shows(show_list) that takes a list of show tuples as defined above and prints in order of start time the list of shows that Angusina should attend, as obtained using the algorithm in the lecture notes. Shows are printed one per line with the title, start and end times separated by a space as shown in the example. To ensure a unique solution, you may assume that show end times are unique.
This is the pseudocode I must use:
Sort jobs by finish times: f1 <= f2 <=...fn
S = {}
t_current = 0 (Finish time of the last job selected)
for j = 1...n:
if sj >= t_current:
S = S U {j}
t_current = fj
return S
My test code is:
print_shows([ ('a', 0, 6), ('b', 1, 3), ('c', 3, 2), ('d', 3, 5), ('e', 4, 3), ('f', 5, 4), ('g', 6, 4), ('h', 8, 3)])
My result should be:
b 1 4
e 4 7
h 8 11
I am not sure how to read the pseudocode?
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
