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
Question
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
Solution
This problem can be solved using a priority queue and sorting. Here are the steps to solve this problem:
-
Sort the
processorTimearray in ascending order. This will allow us to assign tasks to the processors in the order they become available. -
Create a priority queue to store the tasks. The priority queue should be a max heap, meaning the largest element is always at the top. This is because we want to assign the longest tasks first.
-
Sort the
tasksarray in descending order and add all the tasks to the priority queue. -
For each processor in
processorTime, remove four tasks from the priority queue and calculate the time it takes for the processor to complete these tasks. This is done by adding the processor's available time to the time it takes to complete the task. Keep track of the maximum time it takes for any processor to complete its tasks. -
The maximum time it took for any processor to complete its tasks is the minimum time when all of the tasks
Similar Questions
You are given a job that has been divided 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 in 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 FormatThe first line of input contains T - the number of test cases. It's followed by 2T lines. The first line of each test case contains N and K - the 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.Output FormatFor each test case, print the minimum possible time in which you can complete the job, separated by a new line.Constraints50 points1 <= N,K <= 20100 points1 <= N,K <= 10000General Constraints1 <= T <= 501 <= Si <= 103ExampleInput610 31 10 13 4 5 12 23 12 18 88 417 27 22 45 26 32 45 162 274 617 374 24 61 81 66 76 512 154 104 215 30 10 50Output3866741596455ExplanationTest Case 1: The arrangement for which we can achieve minimum possible time is as follows:[1 10 13 4 5] - Worker 1[12 23] - Worker 2[12 18 8] - Worker 3Test Case 2: The arrangement for which we can achieve minimum possible time is as follows:[17 27 22] - Worker 1[45] - Worker 2[26 32] - Worker 3
multi core processing
CPU Scheduling algorithms should ideally be optimised such that:
How many processes can be executed by CPU at one point in time?*1 point4213
For multicore processors to be used effectively, computers must understand how to divide tasks into parts that can be distributed across each core—an operation called ________blank.Multiple Choiceparallel processinggraphic coprocessingmulticore processingmicro processing
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.