Suppose you have one machine and a set of n jobs a1 , a2 , · · · , an to process on that machine.
Each job aj has a processing time tj , a pro?t pj , and a deadline dj . The machine can process only one job at a time, and job aj must run uninterruptedly for tj consecutive time units. If job aj is completed by its deadline dj , you receive a profit pj , but if it is completed after its
deadline, you receive a profit of 0. Give an algorithm to find the schedule that obtains the maximum amount of profit, assuming that all processing times are integers between 1 and n.