Compute an Optimum Assignment of Tasks

EPI #18.1

Description:

Assign tasks to workers. Each work gets two tasks. Arrange the assignments so that the total working time is minimized.

Example:

task duration is [5,2,1,6,4,4]
assignment:
(5+2, 1+6, 4+4)
total working time is 8

Idea:

Greedy.

First sort, then largest pair with smallest.

Code:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int greedy(vector<int> arr){
    sort(arr.begin(), arr.end());
    int i=0; 
    int j=arr.size()-1;
    int totalTime=INT_MIN;
    while(i<j){
        int localSum = arr[i]+arr[j];
        totalTime = max(totalTime, localSum);
        i++;
        j--;
    }
    return totalTime;
}

int main(){
    vector<int> arr={5,2,1,6,4,4};
    cout<<greedy(arr);
}