Problem 5. (10 marks) In this problem we have one machine and a set of n jobs ai,... ,an to run on this machine. Each job ai has a processing time ti, profit pi, and a deadline di. We can process only one job at a time on this machine and we cannot interrupt a job once started. A job that is completed by its deadline di returns a profit of pi, otherwise the profit is zero. Our goal is to find a subset J of jobs and a schedule for them (start/finish time for each job in J) with maximum profit. a) Prove that there is an optimum solution J such that the jobs in J are scheduled in increasing order of their deadline. b) Describe an algorithm to find a schedule with maximum profit. You may assume that the processing times are integers in [1,.. .,n]. Do the analysis of the running time as well