DES Pune University, Pune
School of Engineering and Technology
Department of Computer Science and Engineering
Program: B. Tech Computer Science & Engineering
Academic Year: 2025-26 Year: Third Year Term: I
PRN No.: 1012412052 Name: Pradnya Wagh
Subject: DAA
Assignment No.: 4
Date:
Lab Assignment: 04
Title:-Consider the scheduling problem. n tasks to be scheduled on single processor. Let
d1, ...,dn be deadline and p1,....pn be the profit of each task to execute on single
processor is known. The tasks can be executed in any order but one task at a time and
each task take 1 unit of time to execute. Design a greedy algorithm for this problem and
find a schedule or sequence of jobs that gives maximum profit.
Theory:
Greedy Approach — Concept
The key idea of the greedy algorithm is:
1. Sort all jobs in descending order of profit — because we want to take the most
profitable jobs first.
2. For each job, try to assign it to the latest possible time slot before its deadline (if
available).
This ensures we don’t block earlier slots unnecessarily.
3. If no slot is free before the deadline, we skip that job.
This approach ensures maximum profit while maintaining valid scheduling constraints.
Algorithm Design (Steps)
Step 1: Sort the jobs based on decreasing profit.
Assignment By:1012412052 Page 1 of 5
DES Pune University, Pune
School of Engineering and Technology
Department of Computer Science and Engineering
Program: B. Tech Computer Science & Engineering
Step 2: Find the maximum deadline (say max_deadline).
Step 3: Create a time slot array of size max_deadline to keep track of which slot is filled.
Step 4: For each job in sorted order:
● Check from its deadline backward to find a free slot.
● If a slot is free, assign the job to that slot.
Step 5: Return the sequence of scheduled jobs and the total profit.
Code:
class Job:
def __init__(self, job_id, deadline, profit):
self.id = job_id
self.deadline = deadline
self.profit = profit
def job_sequencing(jobs):
# Step 1: Sort by profit (descending order)
jobs.sort(key=lambda x: x.profit, reverse=True)
# Step 2: Find max deadline
max_deadline = max(job.deadline for job in jobs)
slot = [-1] * (max_deadline + 1)
total_profit = 0
job_order = []
Assignment By:1012412052 Page 2 of 5
DES Pune University, Pune
School of Engineering and Technology
Department of Computer Science and Engineering
Program: B. Tech Computer Science & Engineering
# Step 3: Schedule jobs
for job in jobs:
# Try to schedule at the latest possible slot
for j in range(job.deadline, 0, -1):
if slot[j] == -1:
slot[j] = job.id
total_profit += job.profit
job_order.append(job.id)
break
print("Scheduled Job Order:", job_order)
print("Total Profit:", total_profit)
# Example
jobs = [
Job('A', 2, 100),
Job('B', 1, 19),
Job('C', 2, 27),
Job('D', 1, 25),
Job('E', 3, 15)
job_sequencing(jobs)
Assignment By:1012412052 Page 3 of 5
DES Pune University, Pune
School of Engineering and Technology
Department of Computer Science and Engineering
Program: B. Tech Computer Science & Engineering
Output:
After sorting by profit (descending):
A(100), C(27), D(25), B(19), E(15)
Available time slots: [1, 2, 3]
Scheduling Process:
● Job A → placed at slot 2 (deadline 2)
● Job C → placed at slot 1 (deadline 2)
● Job D → no free slot before deadline 1 → skipped
● Job B → skipped (no free slot)
● Job E → placed at slot 3 (deadline 3)
Final Job Sequence: [C, A, E]
Total Profit = 27 + 100 + 15 = 142
Conclusion
Assignment By:1012412052 Page 4 of 5
DES Pune University, Pune
School of Engineering and Technology
Department of Computer Science and Engineering
Program: B. Tech Computer Science & Engineering
The Job Sequencing with Deadlines problem demonstrates the efficiency of the Greedy
approach.
By always choosing the most profitable job first and placing it in the latest possible slot,
we ensure that every local decision contributes to the global optimum.
Assignment By:1012412052 Page 5 of 5
