This article will go over how to implement the interval scheduling algorithm in Python. Let’s get started with an overview of the interval scheduling algorithm.
What is Interval Scheduling Algorithm?
In the domain of algorithm design, interval scheduling is a class of problems. The programs take a number of tasks into account. Every task is represented by an interval that indicates the amount of time it should take a machine to complete it. If there is no overlap between any two intervals on the system or resource, a subset of intervals is compatible.
The goal of the interval scheduling maximization problem is to identify the largest compatible set or a collection of intervals with the least possible overlap. The idea is to optimize throughput by completing as many tasks as you can.
Interval Scheduling Problem:
Input – An input of n intervals {s(i), … , f(i)−1} for 1 ≤ i ≤ n where i represents the intervals, s(i) represents the start time, and f(i) represents the finish time.
Output – A schedule S of n intervals where no two intervals in S conflict, and the total number of intervals in S is maximized.
Suppose we have a list of events, Each event is in the format [a,b], where a is the starting time and b Is the ending time. A person can only be at one of these events at a time, and they can immediately go from one event to another. If two events have coinciding stop and start times, respectively. Find the greatest number of events that a person can attend.
intervals = [4,5], [0,2], [2,7], [1,3], [0,4]]
In this problem, we must determine the maximum number of events that an individual can attend. Examine the diagram below to see how the person can attend as many events as possible.
Given intervals
Consider the following scenario, If a person attends an event at intervals (4,5) and (0,2), he will be unable to attend events at intervals (2,7), (1,3), and (0,4), so the maximum number of events will be two.
Consider and observe carefully. If we want to attend as many events as possible, we should attend small events that will be completed in a short period of time. Attending an event with a longer time span will not be beneficial because we will be unable to attend other events due to the overlapping of the intervals. Try to choose the events with the shortest duration first.
How we can achieve this goal?
The option is to store all the intervals in a list and sort the list items based on the ending time.
Initial List - [ (4,5), (0,2), (2,7), (1,3), ( 0,4) ] sorted list - [ (0,2), (1,3), (0,4), (4,5), (2,7) ]
How the sorted graph will look like using diagram is shown below:
Sorted intervals
According to the graph, we can attend (0,2) and (4,5) events, but the rest are still overlapping. Now we will run the program for the intervals.
Python3
intervals = [(4, 5), (0, 2), (2, 7), (1, 3), (0, 4)] # sorting the intervals intervals.sort(key=lambda x: x[1]) # print(intervals) # counting the events count = 0# keeping track of ending of intervals end = 0# list of the intervals in which person will attend the events answer = [] # traversing the list of intervals for interval in intervals: # starting time of next interval will >= ending # time of previous interval if(end <= interval[0]): # update the and end = interval[1] # increment the count by one count += 1 # insert the non-conflict interval in the list answer.append(interval) # print statements will print non-conflict # intervals count as well intervals print("The maximum events a person can attend is : ", count) print("List of intervals in which person will attend events : ", answer) |
Output:
('The maximum events a person can attend is : ', 2)
('List of intervals in which person will attend events : ', [(0, 2), (4, 5)])
Example 1:
Step 1: In the first step, we are storing the intervals in the list.
Python3
# list of intervals intervals = [(1, 3), (7, 12), (2, 5), (6, 18), (14, 16)] |
Step 2: In this step, we are sorting the list of tuples based on the ending time or second element of each tuple. Lambda is a small function that allows you to pass any number of arguments but the expression should be in one single line. In the above situation, the lambda function is accessing the second element of the tuple inside the intervals list and passes it as a key to the sort function so that the tuple will be sorted according to the second element in ascending order.
Python3
# list of intervals intervals = [(1,3),(7,12),(2,5),(6,18),(14,16)] # sorting the intervals intervals.sort(key = lambda x : x [1]) print(intervals) |
Output:
[(1, 3), (2, 5), (7, 12), (14, 16), (6, 18)]
Step 3: Now we are initializing the count, and end variables by zero. The count and end will be changed in the program according to the conditions. The count will tell us the count of the maximum number of intervals without conflict and the end will help us to keep track of the intervals. We will store the non-conflict intervals in the answer list.
Python3
# counting the events count = 0 # keeping track of ending of intervals end = 0 # list of the intervals in which person will attend the events answer = [] |
Step 3: In this particular step, we are traversing each interval one by one and checking whether the start time of the next interval is greater than or equal to the end time of the previous interval or not. if true we are incrementing the count by one and inserting that interval into the answer list, we are doing this because there should not be any conflict and as we already sorted the intervals based on the ending time of the intervals so we are attending the sort period intervals first so that we can maximize the answer. In last we are just printing the count of non-conflict intervals as well as the non-conflict intervals as a list
Python3
# list of intervals intervals = [(1, 3), (7, 12), (2, 5), (6, 18), (14, 16)] # sorting the intervals intervals.sort(key=lambda x: x[1]) # print(intervals) # counting the events count = 0 # keeping track of ending of intervals end = 0 # list of the intervals in which person will attend the events answer = [] # traversing the list of intervals for interval in intervals: # starting time of next interval will >= ending time of previous interval if(end <= interval[0]): # update the and end = interval[1] # increment the count by one count += 1 # insert the non-conflict interval in the list answer.append(interval) # print statements will print non-conflict intervals count as well intervals print("The count of Non-conflict intervals : ", count) print("List of the intervals : ", answer) |
Output:
('The count of Non-conflict intervals : ', 3)
('List of the intervals : ', [(1, 3), (7, 12), (14, 16)])
Example 2:
In this example, it’s clearly visible that each previous interval’s end time is equal to the start time of the next interval means without any conflict we can schedule the work for each interval hence the answer will be the number of intervals only which is 5.
Python3
intervals = [(2, 5), (5, 10), (10, 20), (20, 30), (30, 45)] # sorting the intervals intervals.sort(key=lambda x: x[1]) print(intervals) # counting the events count = 0# keeping track of ending of intervals end = 0# list of the intervals in which person will attend the events answer = [] # traversing the list of intervals for interval in intervals: # starting time of next interval will >= ending time of previous interval if(end <= interval[0]): # update the and end = interval[1] # increment the count by one count += 1 # insert the non-conflict interval in the list answer.append(interval) # print statements will print non-conflict intervals count as well intervals print("The count of non-overlapping events : ", count) print("List of intervals without overlapping : ", answer) |
Output:
[(2, 5), (5, 10), (10, 20), (20, 30), (30, 45)]
('The count of non-overlapping events : ', 5)
('List of intervals without overlapping : ', [(2, 5), (5, 10), (10, 20), (20, 30), (30, 45)])
Example 3:
In this example intervals are not according to our requirement so the intervals will be sorted in a manner such that minimum period intervals will in starting and then greater, greater, and greater intervals will be there. So this is how the intervals will look after sorting – [(3, 5), (4, 5), (6, 8), (10, 11), (2, 12), (9, 12), (11, 12)]. As you can see 1st, 3rd, 4th and 7th intervals are not overlapping each other so the maximum number of intervals without conflict will be 4.
Python3
intervals = [(2, 12), (3, 5), (4, 5), (6, 8), (9, 12), (10, 11), (11, 12)] # sorting the intervals intervals.sort(key=lambda x: x[1]) print(intervals) # counting the events count = 0# keeping track of ending of intervals end = 0# list of the intervals in which person will attend the events answer = [] # traversing the list of intervals for interval in intervals: # starting time of next interval will >= ending time of previous interval if(end <= interval[0]): # update the and end = interval[1] # increment the count by one count += 1 # insert the non-conflict interval in the list answer.append(interval) # print statements will print non-conflict intervals count as well intervals print("The count of non-overlapping events : ", count) print("List of intervals without overlapping : ", answer) |
Output:
[(3, 5), (4, 5), (6, 8), (10, 11), (2, 12), (9, 12), (11, 12)]
('The count of non-overlapping events : ', 4)
('List of intervals without overlapping : ', [(3, 5), (6, 8), (10, 11), (11, 12)])
Example 4:
In this example, the sorted intervals list will look like this – [(1, 2), (2, 3), (2, 4), (1, 6), (4, 9), (5, 10)]. We can observe that the 1st,2nd, and 5th intervals are not overlapping so the maximum number of intervals without overlapping will be 3.
Python3
intervals = [(1, 6), (2, 3), (5, 10), (1, 2), (2, 4), (4, 9)] # sorting the intervals intervals.sort(key=lambda x: x[1]) print(intervals) # counting the events count = 0# keeping track of ending of intervals end = 0# list of the intervals in which person will attend the events answer = [] # traversing the list of intervals for interval in intervals: # starting time of next interval will >= ending time of previous interval if(end <= interval[0]): # update the and end = interval[1] # increment the count by one count += 1 # insert the non-conflict interval in the list answer.append(interval) # print statements will print non-conflict intervals count as well intervals print("The count of non-overlapping events : ", count) print("List of intervals without overlapping : ", answer) |
Output:
[(1, 2), (2, 3), (2, 4), (1, 6), (4, 9), (5, 10)]
('The count of non-overlapping events : ', 3)
('List of intervals without overlapping : ', [(1, 2), (2, 3), (4, 9)])
