Ch-Assignment2-JobSequence

def job_sequencing(jobs):
    # sort jobs by profit in descending order
    jobs.sort(key=lambda x: x[2], reverse=True)
    # Calculate the maximum deadline
    max_deadline = max(jobs, key=lambda x: x[1])[1]
    # To keep track of free time slots
    result = [False] * max_deadline
    total_profit = 0

    for job in jobs:
        deadline = job[1] - 1
        while deadline >= 0:
            if not result[deadline]:
                result[deadline] = True
                total_profit += job[2]
                break
            deadline -= 1

    return total_profit

jobs = [
    (1, 5, 95),
    (2, 2, 15),
    (3, 7, 25),
    (4, 1, 40),
    (5, 5, 80),
    (6, 4, 50),
    (7, 2, 10),
    (8, 3, 35),
    (9, 4, 55)
]

max_profit = job_sequencing(jobs)
print("Maximum profit:", max_profit)