Recall the basic scheduling problem, where we have a set of n jobs (e.g., homework assignments) such that each job j is associated with a size sj and a deadline dj , and a machine that can process one unit of job per time slot. The goal is to find an assignment of jobs to time slots such that: (1) each job gets a number of time slots that equals its size; (2) each job is completed on or before its corresponding deadline. In this question, we will consider a variant of the basic problem, where the machine is lazy in the sense that it needs to rest for one time slot after completing each job. For example, if the machine processes job 1 from time 1 to time 5, then we cannot schedule any job at time 6, and may resume processing other jobs at time 7. Is the earliest deadline first greedy algorithm still optimal (in the sense of the claim proved on page 3 of slides S12)? If yes, justify your answer. If no, give a counter example.

Recall the basic scheduling problem, where we have a set of n jobs (e.g., homework assignments) such that each job j is associated with a size s; and a deadline dj, and a machine that can process one unit of job per time slot. The goal is to find an assignment of jobs to time slots such that: (1) each job gets a number of time slots that equals its size; (2) each job is completed on or before its corresponding deadline. In this question, we will consider a variant of the basic problem, where the machine is "lazy" in the sense that it needs to rest for one time slot after completing each job. For example, if the machine processes job 1 from time 1 to time 5, then we cannot schedule any job at time 6, and may resume processing other jobs at time 7. Is the earliest deadline first greedy algorithm still optimal (in the sense of the claim proved on page 3 of slides $12)? If yes, justify your answer. If no, give a counter example. Recall the basic scheduling problem, where we have a set of n jobs (e.g., homework assignments) such that each job j is associated with a size s; and a deadline dj, and a machine that can process one unit of job per time slot. The goal is to find an assignment of jobs to time slots such that: (1) each job gets a number of time slots that equals its size; (2) each job is completed on or before its corresponding deadline. In this question, we will consider a variant of the basic problem, where the machine is "lazy" in the sense that it needs to rest for one time slot after completing each job. For example, if the machine processes job 1 from time 1 to time 5, then we cannot schedule any job at time 6, and may resume processing other jobs at time 7. Is the earliest deadline first greedy algorithm still optimal (in the sense of the claim proved on page 3 of slides $12)? If yes, justify your answer. If no, give a counter example