You are given a job which has been divide into N tasks. The task cannot be divided any further. Each of the N tasks takes Si number of seconds to complete. Your job will be completed when all your tasks are completed. You have K workers at your disposal to help you complete the tasks. But as per the nature of the job, a worker can only be allocated continuous tasks. A worker can work only on a single task at any given point of time. However, the workers can work in parallel on different tasks. You have to find the minimum possible time in which you can complete the job.Input FormatFirst line of input contains T - number of test cases. Its followed by 2T lines. First line of each test case contains N and K - number of tasks and available workers for the current job, separated by space. The next line contains N positive integers - denoting the time taken to complete the ith task.Constraints50 points1 <= N,K <= 20150 points1 <= N,K <= 10000General Constraints1 <= T <= 501 <= Si <= 103Output FormatFor each test case, print the minimum possible time in which you can complete the job, separated by newline.Sample Input 0610 31 10 13 4 5 12 23 12 18 8 8 417 27 22 45 26 32 45 16 2 274 61 7 374 24 61 81 66 76 51 2 154 10 4 215 30 10 50 Sample Output 03866741596455Explanation 0Self Explanatory
Question
You are given a job which has been divide into N tasks. The task cannot be divided any further. Each of the N tasks takes Si number of seconds to complete. Your job will be completed when all your tasks are completed. You have K workers at your disposal to help you complete the tasks. But as per the nature of the job, a worker can only be allocated continuous tasks. A worker can work only on a single task at any given point of time. However, the workers can work in parallel on different tasks. You have to find the minimum possible time in which you can complete the job.Input FormatFirst line of input contains T - number of test cases. Its followed by 2T lines. First line of each test case contains N and K - number of tasks and available workers for the current job, separated by space. The next line contains N positive integers - denoting the time taken to complete the ith task.Constraints50 points1 <= N,K <= 20150 points1 <= N,K <= 10000General Constraints1 <= T <= 501 <= Si <= 103Output FormatFor each test case, print the minimum possible time in which you can complete the job, separated by newline.Sample Input 0610 31 10 13 4 5 12 23 12 18 8 8 417 27 22 45 26 32 45 16 2 274 61 7 374 24 61 81 66 76 51 2 154 10 4 215 30 10 50 Sample Output 03866741596455Explanation 0Self Explanatory
Solution
The problem is about task scheduling with multiple workers. Here are the steps to solve it:
-
Understand the problem: You have a certain number of tasks, each with a specific time to complete. You also have a certain number of workers. Each worker can only work on continuous tasks and can only work on one task at a time. However, multiple workers can work on different tasks at the same time. The goal is to find the minimum possible time to complete all tasks.
-
Input: The first line of input contains the number of test cases. Each test case has two lines. The first line contains the number of tasks and the number of workers. The second line contains the time taken to complete each task.
-
Output: For each test case, you need to print the minimum possible time to complete all tasks.
-
Approach: This problem can be solved using binary search. The low limit of the binary search is the maximum time of any task and the high limit is the sum of times of all tasks. For each mid value (which is the candidate for the answer), check if it is possible to finish all tasks within 'mid' time with the given number of workers. If it is possible, then try to minimize the time further, else try to increase the time.
-
Implementation: Implement the above approach in your preferred programming language.
-
Test: Test your solution with various test cases to ensure it works as expected.
This is a typical problem of task scheduling and can be solved using binary search and greedy algorithms.
Similar Questions
Given a set of N jobs where each jobi has a deadline and profit associated with it.Each job takes 1 unit of time to complete and only one job can be scheduled at a time. We earn the profit associated with job if and only if the job is completed by its deadline.Find the number of jobs done and the maximum profit.Note: Jobs will be given in the form (Jobid, Deadline, Profit) associated with that Job.
You are given an integer N denoting an N×N matrix. Initially, each cell of the matrix isempty. You are given K tasks. In each task, you are given a cell (i, j) where cell (i, j)represents the ithrow and jth column of the given matrix.You have to perform each task sequentially in the given order. Each task is describedin cell (i, j). For each task, you have to place X in each cell of row i and each cellcolumn j. After you complete each task, you are required to print the number ofempty cells in the matrix.
The following table shows jobs to be processed at a machine. Determine the processing sequence that will minimize total number of late jobs. Job Processing Time (days) Due Date (days) A 3 4 B 2 5 C 5 10 D 2 11 E 4 13 F 9 201. Job is the first job that is late in the given sequence.2. Job has the largest processing time out of these 5 jobs.3. Optimal sequence is with on
he minimum time required to complete the taskThe maximum time required to complete the taskThe most likely time required to complete the taskThe earliest possible start time for the task
You have n processors each having 4 cores and n * 4 tasks that need to be executed such that each core should perform only one task.Given a 0-indexed integer array processorTime representing the time at which each processor becomes available for the first time and a 0-indexed integer array tasks representing the time it takes to execute each task, return the minimum time when all of the tasks have been executed by the processors.Note: Each core executes the task independently of the others. Example 1:Input: processorTime = [8,10], tasks = [2,2,3,1,8,7,4,5]Output: 16Explanation: It's optimal to assign the tasks at indexes 4, 5, 6, 7 to the first processor which becomes available at time = 8, and the tasks at indexes 0, 1, 2, 3 to the second processor which becomes available at time = 10. Time taken by the first processor to finish execution of all tasks = max(8 + 8, 8 + 7, 8 + 4, 8 + 5) = 16.Time taken by the second processor to finish execution of all tasks = max(10 + 2, 10 + 2, 10 + 3, 10 + 1) = 13.Hence, it can be shown that the minimum time taken to execute all the tasks is 16.Example 2:Input: processorTime = [10,20], tasks = [2,3,1,2,5,8,4,3]Output: 23Explanation: It's optimal to assign the tasks at indexes 1, 4, 5, 6 to the first processor which becomes available at time = 10, and the tasks at indexes 0, 2, 3, 7 to the second processor which becomes available at time = 20.Time taken by the first processor to finish execution of all tasks = max(10 + 3, 10 + 5, 10 + 8, 10 + 4) = 18.Time taken by the second processor to finish execution of all tasks = max(20 + 2, 20 + 1, 20 + 2, 20 + 3) = 23.Hence, it can be shown that the minimum time taken to execute all the tasks is 23. Constraints:1 <= n == processorTime.length <= 250001 <= tasks.length <= 1050 <= processorTime[i] <= 1091 <= tasks[i] <= 109tasks.length == 4 * n
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.