Puzzles for Programmers and Pros

6.3. Finding a Schedule That Works

You have a set of tasks for a robot. There is no precedence constraint requiring any task to be completed before another. Each requires a certain amount of time and has a certain deadline. Your predecessor assures you there is enough time for the robot to do everything, but he doesn't remember how. (His lack of organization explains why he is your predecessor and not your boss.) You have to arrange things so your robot finishes each task by its deadline.

1. In which order do you schedule the tasks starting from current day 0?

   Task T1 takes 4 days with deadline on day 45

   Task T2 takes 4 days with deadline on day 48

   Task T3 takes 5 days with deadline on day 25

   Task T4 takes 2 days with deadline on day 49

   Task T5 takes 5 days with deadline on day 36

   Task T6 takes 2 days with deadline on day 31

   Task T7 takes 7 days with deadline on day 9

   Task T8 takes 5 days with deadline on day 39

   Task T9 takes 4 days with deadline on day 13

   Task T10 takes 6 days with deadline on day 17

   Task T11 takes 4 days with deadline on day 29

   Task T12 takes 1 day with deadline on day 19

NOTE

The best algorithm for this problem has the very suggestive name: "Earliest Deadline First."

6.3.1. Solution to Finding a Schedule That Works

1. In which order do you schedule the tasks starting from current day 0?

This is a situation where you don't want the computer to explore all cases, trying all 12! Orderings might take a while and would be completely impractical if there were even 20 tasks. As alluded ...