Job Sequencing with deadlines is an activity selection problem. Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. Greedy algorithms are used for optimization problems. An optimization problem can be solved using Greedy if the problem has the following property: At every step, we can make a choice that looks best at the moment, and we get the optimal solution of the complete problem
In this tutorial, I am going to show you how to solve a greedy problem. In this problem, Given an array of jobs where every job has a deadline and associated profit if the job is finished before the deadline. It is also given that every job takes a single unit of time, so the minimum possible deadline for any job is 1. How to maximize total profit if only one job can be scheduled at a time.
Look at this image, we are going to find the maximum job sequence.
Algorithm of Job Sequcence
- Sort the activities in ascending order according to their finishing order.
- Select the first activity from the sorted list and print it
- Do same task if the start time of this activity is greater than or equal to the finish time of previous activity
So according to this image, our output will be BECD. Why BECD? Well, Look at this sorted array, In this array the first activity is B then E. E’s start time is greater than the B. Then the next activity is A whose start time smaller than B, so we can’t print A according to our conditions. We do the same task repeatedly until the activity is ended.
Code of Job Sequencing with deadlines
def optimal_solution(list): print(list, end=" ") temp = list for i in range(1, len(list)): if temp <= list[i]: temp = list[i] print(list[i], end=" ")
The optimal solution method is the main function of this algorithm. Inside the function, first I print the first actively then store this activity in a temporary variable. After then I execute a loop, inside the loop I compared conditions according to our algorithm.
def bubble_sort_asc(list): for i in range(0, len(list)): for j in range(i+1, len(list)): if list[i] > list[j]: list[i], list[j] = list[j], list[i] def optimal_solution(list): print(list, end=" ") temp = list for i in range(1, len(list)): if temp <= list[i]: temp = list[i] print(list[i], end=" ") activities = [ (0, 6, "A"), (1, 2, "B"), (5, 7, "C"), (8, 9, "D"), (3, 4, "E"), (5, 9, "F"), ] bubble_sort_asc(activities) optimal_solution(activities)