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
'''