Question 1 (Job Sequencing - 5 points) You are given a set of n jobs S where each job si E S has a profit pi and a deadline d. Each job takes one unit of time to complete and you can only work on one job at a time. You can work on a job on anytime no later than its deadline. For erample, if a job has a deadline of 5, you can work on it on any time t 5. Your goal is to find the sequence of jobs to work on so as to maximize your profit. Assume that you will work on the first job at t = 0. For example, given a set of 10 jobs with profits P = (15,2,18,1, 25, 20, 8, 10, 12,5) and deadlines D (9,2,5, 7, 4, 2,5,10,4, 3), the output should be to run the sequence of jobs with ids (7,6,9,5, 3, 4, 1,8) in this order to get a profit of 109. The figure below illustrates the input and output of this example. Notice that jobs #2 and #10 have been dropped. #6 #9 #7 200 12 8 #2 #10 #5 #3 #4 #1 #8 2 5 25 18 15 101 t Input: 5 10 #6 #9 #5 #3 #4 #1 #8 8 20 12 25 18 1 15 10 Optimal answer: Pi 1. Describe a greedy algorithm for the job sequencing algorithm. No pseudo code is needed. 2. Prove the optimality of your greedy algorithm. 3. Apply your algorithm to the following problem. di 154 2 7 6 2 5 4 1 2 5 7 3 2 1 7 4 8 3 4 1 6 Ooo