Problem Link - Processor Scheduling
Problem statement
There are N+M jobs waiting to be run on a processor. N of these are classified jobs: C_1, C_2, \ldots, C_N, and the other M are public jobs: P_1, P_2, \ldots, P_M. There can only be one job running on the processor at any given millisecond (ms). Once the processor starts running a job, it has to finish it completely before starting any other job.
C_i takes time q_i milliseconds (ms) to finish. Also, for 1 \leq i \leq N, C_i can be started only after C_1, C_2, \cdots, C_{i-1} have finished.
P_j takes p_j ms to finish. These jobs can be run in any order. The classified and public jobs can also be interleaved in any order. However, sources have reported that for all 1 \leq j \leq M, there may be an interrupt signal sent to the processor by an alien spaceship at time t_j. In order to remain on good terms with the aliens, the processor is required to be running the public job P_j at time t_j. In other words, each of the M public jobs need to be scheduled such that for 1 \leq j \leq M, if P_j starts at the s_j-th millisecond, then s_j \leq t_j \lt s_j+p_j.
You want to finish all the jobs as soon as possible. You can start assigning jobs from time 1. Please find the minimum time (in ms) by which all the N+M jobs can be finished. If it is not possible to finish all the jobs while satisfying the rules, output -1 instead.
Approach
The problem can be approached by using dynamic programming. We need to handle two types of jobs: classified jobs, which need to be scheduled in order, and public jobs, which must be scheduled to satisfy specific time constraints.
First, we sort the public jobs based on their interrupt times because we need to ensure that these jobs are done at specific times. We will track the state of the jobs using dynamic programming, where dp[i] represents the minimum time required to complete the first i public jobs while considering the classified jobs as well.
We begin by iterating through each public job and updating the minimum time required to finish all the jobs. For each classified job, we update the possible states based on whether we can finish the classified job before the next public job or whether we need to consider the time constraints for the public jobs.
By managing the order in which jobs are completed and ensuring the constraints for public jobs are respected, we can compute the minimum time to finish all jobs or determine that it is impossible to do so.
Time Complexity
The time complexity is O(N \times M), where N is the number of classified jobs and M is the number of public jobs, due to the nested iteration over both classified and public jobs.
Space Complexity
The space complexity is O(M), as we are using arrays to store dynamic programming states for public jobs.