Response
Rookie SRM 16 · 2022-08-22 · by dgoodman
Problem Statement
The jobs are scheduled preemptively, based on the priority of the task to which they belong. Among all the jobs that are ready to execute, the job that is running on the cpu is always a job from the highest priority task. If a job from a higher priority task becomes ready, the currently running job is removed from the cpu and will remain ready to execute, needing only the remainder of its original execution time.
The response time for a job is the time between when it first became ready, and when it completed its execution. Create a class Response that contains a method response that is given int[] period and int[] execution and that returns the response time of the first job of the lowest priority task. If the response time is greater than 1,000,000 or if the first job of the lowest priority task never finishes return -1.
The i-th element of period and the i-th element of execution apply to the i-th task. The tasks are given in order of decreasing priority.
Constraints
- period and execution will both have n elements, where n is between 1 and 50 inclusive.
- The elements of period and execution will be between 1 and 1,000 inclusive.
{20,2,27}
{4,1,8}
Returns: 32
The schedule is as follows, referring to the tasks in order as A, B, and C: The first job of A runs from 0-4. Then the first 5 jobs of B are executed from 4-9. Then C's first job runs from 9-10 and is interrupted at time 10 when B's next job becomes ready. The remaining usage of the processor continues as follows: B:10-11, C:11-12: B:12-13, C:13-14, B:14-15, C:15-16, B:16-17, C:17-18, B:18-19, C:19-20, A:20-24, B:24-29, C:29-30, B:30-31, C:31-32. At this point C has accumulated 8 units of cpu time so its first job has finished executing.
{8,8,8,8}
{3,4,1,1}
Returns: -1
The fourth task will never get a chance to execute. The three higher priority tasks each finish one job every 8 time units and are all ready to execute their next jobs at that time.
{17}
{25}
Returns: 25
The first job of the only task gets to run right away with no interruption. The second job of a task cannot compete for the processor until the previous job of that task has completed.
{10,20,30,40,50}
{2,4,6,8,10}
Returns: 76
{1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000}
{21,22,23,24,25,24,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20}
Returns: 20000
Submissions are judged against all 68 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Response with a public method int response(vector<int> period, vector<int> execution) · 68 test cases · 2 s / 256 MB per case