Dynamic Programming in Python: Optimizing Programs for Efficiency/

...

/

Solution Review: Weighted Scheduling Problem

Solution Review: Weighted Scheduling Problem

In this lesson we will solve the weighted scheduling problem with different techniques of dynamic programming.

We'll cover the following...

Solution 1: Simple recursion #

Press + to interact
# 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 calls and return it (lines 17-18).

As always, let’s take a look at a visualization of the dry run of this algorithm.

Time complexity

At each step, we have two ...