Job Scheduling

job_scheduling_problem.cpp

vector<int> JobScheduling(Job arr[], int n) { 
    vector<int> slots(n, -1);

    sort(arr, arr+n, [&](const Job &a, const Job &b) -> bool {
        return a.profit > b.profit; 
    });

    for(int i=0; i<n; i++) {
        int index = min(arr[i].dead, n)-1;

        while(index >= 0 && slots[index] != -1) index--;

        if(index >=0)
            slots[index] = arr[i].profit;
    }

    int totalProfit = 0;
    int count = 0;

    for(int i=0; i<n; i++) {
        if(slots[i] == -1) continue;

        totalProfit += slots[i];
        count += 1;
    }

    return {count, totalProfit};
}