Jobs Selection¶

O(n^2), O(n)

sort profits decresingly, put slot in remaining , if no slot drop can be improved with disjoint subset

struct Job{
    char id;
    int deadline;
    int profit;
};

bool campare(Job a, Job b){
    return a.profit > b.profit;
}

void selectjobs(struct Job *jobs, int N){

    sort(jobs, jobs+N, campare);

    int result[N];
    int slots[N];

    for(int i = 0; i<N; i++){
        slots[i] = false;
    }

    for(int i = 0; i<N; i++){
        for(int j= min(N, jobs[i].deadline); j>0; j--){
            if(slots[j] == false){
                slots[j] = true;
                result[j] = i;
                break;
            }
        }
    }

    for(int i = 0; i<N; i++){
        if(slots[i])
        cout << jobs[result[i]].id << ", ";
    }

}