Schedule (Greedy) Manually walk through the algorithm 4.4 (pp., 179-180) as demonstrated in example 4.6 to solve the below problem instance. Show each step as shown in the example and then the final value of feasible sequence and profit. Job : 1 2 3 4 5 6 7

Deadline: 2 3 2 4 4 2 1

Profit : 65 50 47 32 30 15 10

4.3 SCHEDULING 179 y, and job y has a smaller (earlier) deadline than job s. If we interchange these two jobs in the sequence, job y will still start by its deadline because it will have started even earlier. And, because the deadline for job z is larger than the deadline for job y and the new time slot given to job a was adequate for job y, job a will also start by its deadline. Therefore, the new sequence will still be feasible. We can prove that the ordered sequence is feasible by repeatedly using this fact while we do an Exchange Sort (Algorithm 1.3) on the original feasible sequence. In the other direction, of course, S is feasible if the ordered sequence is feasible. mle 4.5Suppose we have the jobs in Example 4.4. To determine whether 1,2 4, 7) is feasible, Lemma 4.3 says we need only check the feasibility of the sequence I 2, 7, 1, 4] 1 2 3 3 The deadline of each job has been listed under the job. Because job 4 is not scheduled by its deadline, the sequence is not feasible. By Lemma 4.3, the set is not feasible The algorithm follows. It is assumed that the jobs have already been sorted by profit in nonincreasing order, before being passed to the algorithm Because the profits are needed only to sort the jobs, they are not listed as parameters of the algorithm Scheduling with Deadlines Problem: Determine the schedule with maximum total profit given that each job has a profit that will be obtained only if the job is scheduled by its Algorithm 4.4 deadline Inputs: n, the number of jobs, and array of integers deadline, indexed from 1 to n, where deadlineli] is the deadline for the ith job. The array has been sorted in nonincreasing order according to the profits associated with the obs. Outputs: an optimal sequence J for the job vo id schedule (int m. const int deadline sequence of integer& J)