5.

 
   
 
 #.9.Write program to implement Greedy Algorithm for job sequencing with deadlines.

class Job:
    def __init__(self, job_id, deadline, profit):
        self.job_id = job_id
        self.deadline = deadline
        self.profit = profit

def job_sequencing(jobs):
   
    jobs.sort(key=lambda x: x.profit, reverse=True)
    
 
    max_deadline = max(job.deadline for job in jobs)
    
    
    schedule = [None] * max_deadline
    total_profit = 0
    
     
    for job in jobs:
        
        for j in range(job.deadline - 1, -1, -1):
            if schedule[j] is None:  
                schedule[j] = job.job_id   
                total_profit += job.profit   
                break   

     
    scheduled_jobs = [job_id for job_id in schedule if job_id is not None]
    
    return scheduled_jobs, total_profit

# Example usage
jobs = [
    Job('J1', 2, 100),
    Job('J2', 1, 50),
    Job('J3', 2, 10),
    Job('J4', 1, 20),
    Job('J5', 3, 70)
]

scheduled_jobs, max_profit = job_sequencing(jobs)
print("Scheduled jobs:", scheduled_jobs)
print("Maximum Profit:", max_profit)