brainuser5705

greedy scheduling

Apr 22nd, 2021 (edited)
76
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())
RAW Paste Data Copied