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.

Report
Question

Please briefly explain why you feel this question should be reported.

Report
Cancel

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.

MathJax Example

Answer ( 1 )

  1. Please briefly explain why you feel this answer should be reported.

    Report
    Cancel

Leave an answer

Browse

By answering, you agree to the Terms of Service and Privacy Policy.