Hello, recently I faced with a problem that I have no idea how to solve. The problem goes like this:
A computer has Five(5) processing cores. 'N' processes or jobs come to the cores at a certain time to get processed. Each core has a queue of its own which is used to store jobs. Each job has an 'entry time' and a 'length'. Whenever a core starts processing a job it takes 'length' amount of time to complete. Whenever a job sits on some core's queue it accrues 'waiting time' till it is processed. The 'processing time' of a job is equal to the 'waiting time' plus 'length'. That is:
Processing Time = Waiting Time + Length
(Notice that the 'entry time' is not contained within the 'waiting time'.)
Whichever core will take a certain job is up to us. If a job is selected to be processed by a core but the core is already processing something, the job will enter the core's queue. Our task is to minimize the number of cores used, such the the 'processing time' of every job is less or than equal to ten(10). We cannot skip jobs and the jobs have be processed according to the sequence that they are in the queue.
Input format: First line contains a single integer 'T' equal the number of test cases. (1<=T<=50) For every test case the first line contains a single integer 'N' equal the number of jobs. (1<=N<=1000) The next 'N' lines contain two integers 'E' and 'L' each, showing the 'entry time' and 'length'. (1<=E<=5000 , 1<=L<=10) It is guaranteed for each test case that 'E' appears in non decreasing order.
Output Format: For every test case output in a new line the minimum number of cores required to process all 'N' jobs with the constraint mentioned above. If the number of cores required exceeds five(5), then output "-1" instead.
Additional Constraints: Time limit of five(5) seconds for all test cases combined. Memory limit is 256MB and 1MB for internal stack.
Example Input and Output:
Input: 3 3 1 2 2 3 4 5 7 1 4 1 3 1 2 1 2 2 3 2 4 3 2 6 4 10 5 10 6 10 7 10 8 10 9 10
Output: 1 2 -1
Explanation of test case 1: The first job enters at time 1. The core immediately takes in the job and processes it till time is equal 3. The next job arrives at time equal to 2 and waits for 1 time unit for the core to finish processing the first job. At time equal 4, the core starts processing the second job up till time equal to 7. The third job enters at time equal 4 and waits 3 time units after which the core starts processing it till 12.
Processing time of first job = 0 + 2 = 2. Processing time of second job = 1 + 3 = 4. Processing time of first job = 3 + 5 = 8.
As it can be seen that only one core is required to complete all job such that none of their processing time exceeds 10.
Explanation of test case 2: We can use two cores here: the first core will handle the first, third and the sixth job, while the second core handles the others.
Really hope someone can provide some solutions. Thank you.
