Share
There are N tasks that need to be completed using 2 computers A and B. Each task i has 2 parts that take time: ai (first part) and bi (second part) to be completed. The first part must be completed before starting the second part. Computer A does the first part of all the tasks while computer B does the second part of all the tasks. Computer A can only do one task at a time, while computer B can do any amount of tasks at the same time. Find an O(n log n) algorithm that minimizes the time to complete all the tasks, and give a proof of why the solution obtained by the algorithm is optimal.
ReportQuestion
Please briefly explain why you feel this question should be reported.
There are N tasks that need to be completed using 2 computers A and B. Each task i has 2 parts that take time: ai (first part) and bi (second part) to be completed. The first part must be completed before starting the second part. Computer A does the first part of all the tasks while computer B does the second part of all the tasks. Computer A can only do one task at a time, while computer B can do any amount of tasks at the same time. Find an O(n log n) algorithm that minimizes the time to complete all the tasks, and give a proof of why the solution obtained by the algorithm is optimal.
Answer ( 1 )
Please briefly explain why you feel this answer should be reported.