PLEASE TYPE OUT THE ANSWER!

Analysis of Algorithms:

Problem 3. [Category: Greedy choice proof] We are given n jobs where each job j - takes one unit of server time - is ready from time Ri( an integer 0 ) - will yield a profit Pj(>0) if executed when it is ready (assume that P/=Pj for j=j ) A schedule S assigns to each job j a slot Ti(S) such that RjTi(S) and Ti(S)=Ti(S) for j=i. For each job j we define Dij(S)=Ti(S)Rj. Thus Dij(S)(0) is the "delay" for j in S. Our goal is to find a schedule S that is optimal in that it maximizes V(S)=PjVi(S) where Vi(S) is the value of job j wrt, the schedule S; we expect that Vj(S)=Pj if Di(S)= 0 , and that Vj(S) is bigger if Di(S) is small than if Di(S) is large (details to be provided later). We propose a greedy strategy G: consider the jobs in order of decreasing profit (thus the job with highest profit is considered first), and for each job, schedule it as early as possible after it is ready. 1. First assume that Vj(S)=1+Dj(S)Pj. Show, by means of a counterexample, that G does not always produce an optimal schedule. [10 points] Hint: Consider a example