Created
September 5, 2017 20:00
-
-
Save roychowdhuryrohit-dev/29736dcb4a8741fbb127fa4b5f552b14 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment