LAB ASSIGNMENT-7
Design and Analysis of Algorithm
Name: Arjun Sagar N V
Roll no.:20BCS020
Implementation of Job Scheduling Algorithm using Greedy Method
Code:
#include <stdio.h>
#define MAX 100
typedef struct Job
{
char id[5];
int deadline;
int profit;
} Job;
void jobSequence(Job jobs[], int n);
int minValue(int x, int y)
{
if(x < y) return x;
return y;
}
int main(void)
{
int i, j;
Job jobs[5] =
{
{"j1", 2, 20},
{"j2", 2, 15},
{"j3", 1, 10},
{"j4", 3, 05},
{"j5", 3, 01},
};
Job temp;
int n = 5;
for(i = 1; i < n; i++)
{
for(j = 0; j < n - i; j++)
{
if(jobs[j+1].profit > jobs[j].profit)
{
temp = jobs[j+1];
jobs[j+1] = jobs[j];
jobs[j] = temp;
}
}
}
printf("%10s %10s %10s\n", "Job", "Deadline", "Profit");
for(i = 0; i < n; i++) {
printf("%10s %10i %10i\n", jobs[i].id, jobs[i].deadline, jobs[i].profit);
}
jobSequence(jobs, n);
return 0;
}
void jobSequence(Job jobs[], int n)
{
int i, j, k, maxprofit;
int timeslot[MAX];
int filledTimeSlot = 0;
int dmax = 0;
for(i = 0; i < n; i++)
{
if(jobs[i].deadline > dmax)
{
dmax = jobs[i].deadline;
}
}
for(i = 1; i <= dmax; i++)
{
timeslot[i] = -1;
}
printf("max deadline: %d\n", dmax);
for(i = 1; i <= n; i++)
{
k = minValue(dmax, jobs[i - 1].deadline);
while(k >= 1)
{
if(timeslot[k] == -1)
{
timeslot[k] = i-1;
filledTimeSlot++;
break;
}
k--;
}
if(filledTimeSlot == dmax)
{
break;
}
}
//required jobs
printf("\nRequired Jobs: ");
for(i = 1; i <= dmax; i++) {
printf("%s", jobs[timeslot[i]].id);
if(i < dmax)
{
printf(" > ");
}
}
//required profits
maxprofit = 0;
for(i = 1; i <= dmax; i++) {
maxprofit += jobs[timeslot[i]].profit;
}
printf("\nMax Profit: %d\n", maxprofit);
}
Output:
Time complexity is 𝟐
.
