Task-3
Implement Job Sequencing with deadlines algorithm
Algorithm
Algorithm GreedyJob(d, J, n)
// J is a set of jobs that can be completed by their deadlines.
{
J := {1};
for i := 2 to n do
{
if (all jobs in J ∪ {i} can be completed
by their deadlines) then J := J ∪ {i};
}
}
AlgorithmJS(d,j,n)
{
// d[i] >1,1<i <n arethedeadlines, n >1.Thejobs
// areorderedsuchthat p[\\] >p[2]>>......p[n].J[i]
// istheith jobin theoptimalsolution,1<i <k.
// Also,at terminationd[J[i]] <d[J[i+1]], 1<i <k.
{
d[0] := J[0] := 0; // Initialize.
J[1] := 1; // Include job 1.
k := 1;
for i := 2 to n do
{
// Consider jobs in nonincreasing order of p[i]. Find
// position for i and check feasibility of insertion.
r := k;
while ((d[J[r]] > d[i]) and (d[J[r]] ≠ r)) do r := r - 1;
if ((d[J[r]] ≤ d[i]) and (d[i] > r)) then
{
// Insert i into J[ ].
for q := k to (r + 1) step -1 do J[q + 1] := J[q];
J[r + 1] := i; k := k + 1;
}
}
return k;
}
Program:
class Job:
def __init__(self, job_id, deadline, profit):
self.job_id = job_id
self.deadline = deadline
self.profit = profit
# Function to schedule jobs to maximize profit
def job_sequencing(jobs):
# Step 1: Sort jobs by profit in descending order
jobs.sort(key=lambda job: job.profit, reverse=True)
# Step 2: Initialize an array to keep track of free time slots
max_deadline = max(job.deadline for job in jobs)
slots = [-1] * max_deadline # -1 indicates the slot is free
total_profit = 0
job_sequence = []
# Step 3: Place jobs in available slots to maximize profit
for job in jobs:
# Find a slot for the job, starting from the latest possible slot (deadline)
for j in range(min(job.deadline, max_deadline) - 1, -1, -1):
if slots[j] == -1:
# Slot found
slots[j] = job.job_id
job_sequence.append(job.job_id)
total_profit += job.profit
break
# Output the sequence and profit
return job_sequence, total_profit
# Example usage
jobs = [
Job('Job1', 2, 100),
Job('Job2', 1, 50),
Job('Job3', 2, 10),
Job('Job4', 1, 20),
Job('Job5', 3, 15)
]
# Get the job sequence and total profit
sequence, profit = job_sequencing(jobs)
print("Job sequence:", sequence)
print("Total Profit:", profit)
OUTPUT:
Job Sequence: ['Job1', 'Job2', 'Job5']
Total Profit: 165
(VIVEK'S CODE)
# greedy job sequencing
def greedyJS(d,j,n):
d[0]=j[0]=0
j[1]=1
k=1
for i in range(2,n):
r = k
while d[j[r]]>d[i] and d[j[r]]!=r:
r-=1
if d[j[r]]<=d[i] and d[i]>r:
for q in range(r+1,k-1,-1):
j[q+1]=j[q]
j[r+1]=i
k+=1
return k
def sort(p,d,n):
for i in range(1,n):
k = i
m = p[i]
for j in range(i+1,n):
if(p[j]>m):
m = p[j]
k = j
if i!=k:
d[i],d[k] = d[k],d[i]
p[i],p[k] = p[k],p[i]
n = int(input())
p = [-1]*(n+1)
d = [-1]*(n+1)
for i in range(1,n+1):
p[i],d[i] = map(int,input().split())
sort(p,d,n+1)
print(p[1:])
print(d[1:])
j = [0]*(n+1)
k = greedyJS(d,j,n+1)
print(k)
for i in range(1,k+1):
print(j[i],end=" ")
print()
profit = 0
for i in range(1,k+1):
profit+=p[j[i]]
print(profit)
'''
INPUT:
5
15 2
20 2
10 1
1 3
5 3
OUTPUT:
[20, 15, 10, 5, 1]
[2, 2, 1, 3, 3]
3
1 2 4
40
'''
