Completing tasks on a graph
Hardness
The problem is strongly $NP$-hard so there likely is no fast algorithm solving it.
Consider the 3-Partition problem wherein we are given $3n$ distinct integers $x_1,\ldots, x_{3n}$ and an integer $T$ such that $T/4&lt; x_i&lt; T/2$ and asked to decide whether we can group the $3n$ integers into $n$ groups of $3$ integers with sum equal to $T$ for each triple.
We create an instance of the problem with $4n$ tasks, $3n$ of those tasks having length $x_i$ (one for each $1\leq i\leq 3n$) and $n$ tasks having length $T$.
There exists a solution with no idle time if and only if the 3-Partition instance is solvable. Clearly, if there is a solution to the 3-Partition instance there is a solution to the task planning instance: just have the helper do the length $T$ tasks and have us handle the other tasks in groups of 3 (each with length exactly equal to $T$).
Conversely, in any solution with no idle time, the helper cannot do any task of length less than $T$. If we start the helper on some task with length less than $T$ (i.e., some length $T/4&lt; x_i&lt; T/2$), we must find tasks to do ourselves with length exactly equal to $x_i$. However, no task other than $i$ itself has length $x_i$ (since all the integers $x_i$ are distinct) and for any two integers $x_j,x_k$, $x_j+x_k &gt; T/2 &gt; x_i$.
Thus, in any solution with no idle time, all the tasks done by the helper are of length $T$. The tasks we do ourselves during each task done by the helper must then form a solution to the 3-Partition instance.
Heuristic/approximation
Clearly the idle time cannot be approximated (since it is already hard to decide whether it is non-zero). There is however an EPTAS for the makespan.
Consider the algorithm that always assigns the longest job to the helper, and then fills out the schedule of the master by considering jobs in order of decreasing length and assigning each job that still fits (so that the length of master's schedule does not exceed that of the helper). Repeat this process with the remaining jobs untill all are scheduled. We call a single job done by the helper together with a set of jobs done by the master a &quot;round&quot;.
This yields a solution with idle time of at most $L_\textrm{max}$ where $L_\textrm{max}$ denotes the length of the longest job. To see this, note that if during a round the master is idle for $\epsilon$ units of time, $L_\textrm{max}$ decreases (in the set of remaining jobs) by at least $\epsilon$: if there was a job longer than $L_\textrm{max}-\epsilon$ the master would have done that job and obtained a shorter idle time.
Suppose that the sum of all job lengths is $1$ and let $\epsilon &lt; 1$. If $L_\textrm{max}\leq \epsilon$, the above procedure returns a $1+2\epsilon$-approximation (since the optimal solution has makespan $\geq 1/2$). Otherwise, consider the jobs with length $\geq \epsilon$ of which there are at most $1/{\epsilon}$ (long jobs). Consider also the jobs with $\epsilon &lt;$ length $\geq \epsilon^2$ of which there are at most $1/{\epsilon^2}$ (medium jobs). The remaining jobs (with length $&lt;\epsilon^2$) are called short.
We now, by brute force, enumerate all schedules with the following properties: all long jobs are scheduled, and possibly some medium jobs are scheduled and every round contains at least one long job. For each such schedule, we greedily fill any idle time the master may have with short jobs (so that the master does not work longer than the helper in any round). This is the first phase schdule. We then schedule the remaining short/medium jobs according to the previous greedy algorithm. This is the second phase schedule.
The idle time in the second phase is at most $\epsilon$ (since $L_\textrm{max}&lt; \epsilon$). We now need to bound the additional idle time (over that in an optimal solution) in the first phase.
Take an optimal schedule. If the helper does a short job while the master does a long one, swap the jobs done by the helper and the master -- this does not change the makespan. Delete all short jobs from the schedule and all rounds containing only short/medium jobs. Assume the solution obtained by our approximation algorithm is based on this (modified) schedule, which will be part of the brute force enumeration (so our approximate solution will be at least as good as one obtained from this schedule).
If there are no short jobs in the second phase, then it is easy: We know that the medium jobs scheduled in the second phase do not need to be scheduled together with any long job in an optimal solution. In an optimal case they would be scheduled with at most zero idle time, and the greedy algorithm adds at most $2\epsilon$ extra idle time. We also have not increased the makespan of the brute-force schedule, so it must be optimal.
If there are any short jobs in the second phase, the first phase has at most $1/\epsilon$ rounds (because every round contains a long job) and no phase has more than $\epsilon^2$ idle time for the master (since otherwise we could have scheduled some of the remaining short jobs). Thus the total idle time for the master is at most $\epsilon$. In rounds were the helper has idle time, note that this round is unmodified from the original optimal schedule (since the master would not start a new job if the helper was idle). Thus, the additional idle time, over that of an optimal schedule, is at most $\epsilon$ (from rounds in which the master is idle; the rounds in which the helper is idle do not contribute any additional time).
An interesting question is what happens if the master is impatient and always starts a new job instead of having the option to wait for the helper to finish.