# greedy scheduling

Apr 22nd, 2021 (edited)
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. # names = ['art','eng','math','cs','music']
2. # start_times = [9,9.5,10,10.5,11]
3. # end_times = [10,10.5,11,11.5,12]
4.
5. names = ['a','b','c','d','e','f','g','h']
6. start_times = [0,1,3,3,4,5,6,8]
7. end_times = [6,4,5,8,7,9,10,11]
8.
9. def solve():
10.     global names, start_times, end_times
11.     schedule = []
12.
13.     while(len(names) != 0):
14.
15.         # get the earliest end time
16.         earliest_index = 0
17.         for i in range(1, len(end_times)):
18.             if end_times[i] < end_times[earliest_index]:
19.                 earliest_index = i
20.
21.         schedule.append(names[earliest_index])
22.         earliest_end_time = end_times[earliest_index]
23.
24.         # pop off the earliest class for next iteration
25.         names.pop(earliest_index)
26.         start_times.pop(earliest_index)
27.         end_times.pop(earliest_index)
28.
29.         # getting new lists of valid times
30.         new_names = []
31.         new_start = []
32.         new_end = []
33.         for i in range(len(start_times)):
34.             if start_times[i] >= earliest_end_time: # only if the class starts after the last inputted class ends
35.                 new_names.append(names[i])
36.                 new_start.append(start_times[i])
37.                 new_end.append(end_times[i])
38.
39.         # updates the new classes to consider
40.         names = new_names
41.         start_times = new_start
42.         end_times = new_end
43.
44.     return schedule
45.
46. print(solve())