weighted_job_scheduling.c

#include <stdio.h>
#include <stdlib.h>
typedef struct {
    int startTime, endTime, weight;
} Job;
struct S {
    // current job, last job.
    int cJob, lJob, weight;
} *jobSeq;
// Comparator function to be passed to qsort.
int comparator(const void *a, const void *b) {
    return ((Job *)a) -> endTime - ((Job *)b) ->endTime;
}
// Find last non - conflicting job using binary search.
int lastNonConflict(Job jobs[], int curJob) {
    int lo, hi, mid;
    lo = 0;
    hi = curJob - 1;

    while(lo <= hi) {
	mid = (lo + hi) / 2;
	if(jobs[mid].endTime <= jobs[curJob].startTime) {
	    if(jobs[mid + 1].endTime <= jobs[curJob].startTime) {
		lo = mid + 1;
	    }
	    else {
		return mid;
	    }
	}
	else {
	    hi = mid - 1;
	}
    }

    return -1;
}
// Helper function to display job sequence.
void dispSeq(int endJob) {
    int i = endJob;
    while(i != -1){
	printf("%d <-- ", jobSeq[i].cJob);
	i = jobSeq[i].lJob;
    }
    puts("");
}
// Core part of algortihm.
int findMaxWeight(Job jobs[], int nJobs) {
    int i, lastJob, curWeight, maxWeight, endJob;
    jobSeq = (struct S *)malloc(nJobs*sizeof(struct S));

    // Sort the jobs according to end times.
    qsort(jobs, nJobs, sizeof(Job), comparator);

    jobSeq[0].cJob = 0;
    jobSeq[0].lJob = -1;
    jobSeq[0].weight = jobs[0].weight;
    endJob = 0;

    for(i = 1;i<nJobs;i++) {
	// Calculate weight including current job.
	curWeight = jobs[i].weight;
	// Find last non conflicting job.
	lastJob = lastNonConflict(jobs, i);
	// If latest job found.
	if(lastJob != -1) {
	    curWeight += jobSeq[lastJob].weight;
	}
	if(curWeight>jobSeq[i - 1].weight) {
	    if(lastJob != -1) {
		// If last job exists, store it.
		jobSeq[i].lJob = lastJob;
	    }
	    else {
		jobSeq[i].lJob = -1;
	    }
	    jobSeq[i].cJob = i;
	    jobSeq[i].weight = curWeight;
	    endJob = i;
	}
	else {
	    // Store latest max weight.
	    jobSeq[i].weight = jobSeq[i - 1].weight;
	    jobSeq[i].cJob = -1;
	    jobSeq[i].lJob = -1;
	}
    }
    // Display job sequence.
    dispSeq(endJob);
    maxWeight = jobSeq[nJobs - 1].weight;
    free(jobSeq);
    return maxWeight;
}
// Driver function.
int main() {
    Job arr[] = {{3, 5, 20}, {1, 2, 50}, {6, 19, 100}, {2, 100, 200}};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("Max profit - %d\n", findMaxWeight(arr, n));
    return 0;
}