You are scheduling jobs on processors. You have n jobs, and each job i has an arrival time a_i, and length l_i of cycles that it must be processed, and a deadline d_i. The job must be scheduled for exactly l_i cycles no earlier than time a_i and it must complete by time d_i. Each processor can process exactly one job at a time, and each job can be run on exactly one processor at a time. However, jobs can be interrupted and restarted on the same or a different processor as long as the total time spent processing the job is l_i. In addition, you have k processors and each processor j is available for processing jobs between time s_j and t_j.

Given a set of n jobs and k processors, give an efficient algorithm that either finds a schedule that can complete each job by its deadline or reports that no such schedule exists. Prove the algorithm is correct, and state and justifty the running time.

(For example, we have two jobs. J₁ arrives at time 0, requires 3 cycles, and must complete by time 4. Job J₂ arrives at time 1, requires 2 cycles, and must complete by time 3. We have 2 processors. P₁ is available between times 0 and 4. Processor P₂ is available for times 2 to 3. At time 0 we schedule job J₁ on P₁. At time 1 we interrupt J₁ and run J₂ on P₁. At time 2 we start running J₁ on processor P₂. At time 3, job J₂ is now complete by its deadline, and processor P₂ is no longer available. We interrupt job J₁ and move J₁ to run on processor P₁. At time 4, job J₁ has now run 3 cycles and is complete by its deadline. As a result, we scheduled both jobs to complete by their deadline.