dynamic programming for scheduling meetings of varying length given max available time

optimize_meetings_dp.py

def optimize_meetings(meetings, max_time):
	memo = [[0] * (max_time + 1) for _ in range(len(meetings) + 1)]

	for i in range(len(meetings) + 1):
		if i == 0: continue

		for j in range(max_time + 1):
			cur_mtg = meetings[i - 1]
			index = j - cur_mtg

			if index < 0:
				index = 0
				new_time = 0
			else:
				new_time = memo[i-1][index]
				new_time = new_time + cur_mtg
				if new_time > max_time:
					new_time = 0

			the_max = max(memo[i-1][j], new_time)
			memo[i][j] = the_max

	# Backtrace to find optimal meetings
	used_meetings = []
	j = len(memo[0]) - 1
	reverse_range = range(len(memo))
	reverse_range.reverse()
	for i in reverse_range:
		if memo[i][j] != memo[i-1][j]:
			used_meetings.append(meetings[i - 1])
			j -= meetings[i - 1]

	return memo, used_meetings


if __name__ == '__main__':
	memo, used_meetings = optimize_meetings([3,4,5,9], 15)
	print used_meetings