We have `N`

tasks that need to be scheduled for processing. Each task consists of two parts that need to executed in order. The first one is guarded by a mutex and therefore only one task can be executing this part at a time. The second part has no such constraint and any number of the tasks can be executing this at the same time. For task `i`

we know how much time it needs to spend in each part, namely m_{i} for the guarded part, and a_{i} for the part that can be executed in parallel.

The problem is to find a permutation of the tasks such that the time needed to execute all of them is minimized.

My intuition says that this can be solved with a greedy algorithm, by scheduling the tasks in descending a_{i} order.

For example given the tasks with:

m_{1} = 3, a_{1} = 9

m_{2} = 2, a_{2} = 7

m_{3} = 6, a_{3} = 10

The optimal solution is the permutation 3, 1, 2.

However, I have trouble proving that the greedy solution is optimal. Any ideas on how to do that?