Search⌘ K
AI Features
Home
Courses
Dynamic Programming in Python: Optimizing Programs for Efficiency

Solution Review: Weighted Scheduling Problem

Explore how to solve the weighted scheduling problem using different approaches including simple recursion, top-down memoization, and bottom-up dynamic programming. Understand their time and space complexities and learn how to optimize scheduling efficiently.

We'll cover the following...

Solution 1: Simple recursion

Python 3.5
# Given the index of the class and the list of schedule, this function returns the last class that does not conflict with this class, if it exists otherwise returns None
def lastNonConflict(index, schedule, isSorted = False):
  if not isSorted:
    schedule = sorted(schedule, key=lambda tup: tup[1])
  for i in range(index, -1, -1):
    if schedule[index][0] >= schedule[i][1]:
      return i
  return None
def WSrecursive(schedule, n):
  if n == None or n < 0:  # base case of conflict with the first event
    return 0
  if n == 0:              # base case of no conflict with the first event
    return schedule[n][2]
  
  # find max of keeping the n-th event or not keeping it
  return max(schedule[n][2] + WSrecursive(schedule, lastNonConflict(n, schedule, isSorted= True)), 
          WSrecursive(schedule, n-1))
def WeightedSchedule(schedule):
  # sort the schedule by end time of events
  schedule = sorted(schedule, key=lambda tup: tup[1])
  return WSrecursive(schedule, len(schedule)-1)
  
print(WeightedSchedule([(0, 2, 25), (1, 6, 40), (6, 9, 170), (3, 8, 220)]))

Explanation

To find the profit-maximizing schedule, we need to check all possible schedules. How do we find all possible schedules? This is pretty simple given the fact that you have a helper function, lastNonConflict, that gives us the last event that did not clash with the event provided to it. We sort our schedule with the end times of all the events (line 21). Next, we start from the last event in our sorted schedule, i.e., the event that ended the last. Now if this event is part of the optimal schedule, all the other events that clash with it cannot be part of the optimal schedule. Thus, we find the last non-conflicting event and make a recursive call with it (line 17). Another option could be that this event is not part of the optimal event, so we recursively make a call to the event before it (line 18). In the end, we take the max of these two ...

Time complexity

At each step, we have two possible options to explore. One is to include the event in the schedule, ...