0
$\begingroup$

Given that we have 2 people, and 2n tasks, find the minimum time to complete the tasks. Both persons should solve exactly n tasks each and any task j has to be solved before task j+1. Required time complexity is O(nlogn). E.g- given this input:

A B

5 3

2 1

3 2

1 2

the intended output is 8, because A solves the second and fourth task, and B solves the first and second.

$\endgroup$
3
  • $\begingroup$ Do you have a question? We are a question-and-answer site, so we require you to articulate a specific question about your situation. We're not looking for posts that are just a statement or copy-paste of an exercise-style or coding-contest-style task. $\endgroup$
    – D.W.
    Mar 30, 2020 at 16:30
  • $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$
    – D.W.
    Mar 30, 2020 at 16:30
  • 2
    $\begingroup$ Can you credit the original source where you encountered this task? $\endgroup$
    – D.W.
    Mar 30, 2020 at 16:31

1 Answer 1

1
$\begingroup$

Suppose that the time for completing task $i$ is $a_i$ for $A$ and $b_i$ for $B$. Let $S$ be the set of tasks performed by $B$. The total time required is $$ \sum_i a_i + \sum_{i \in S} (b_i-a_i). $$ Your goal is then to find a subset $S \subseteq [2n]$ of size $n$ which maximizes $\sum_{i \in S} (b_i - a_i)$. You take it from here.

$\endgroup$
1
  • $\begingroup$ Thank you for the help! $\endgroup$
    – stan
    Mar 31, 2020 at 8:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.