How to implement Interval Scheduling algorithm in Python

This Python tutorial helps you to understand what is the interval scheduling algorithm and how Python implements this algorithm. First, we will learn what is interval scheduling algorithm.

Interval Scheduling in Python

Definition :

This algorithm consists of a set of tasks and each task is represented by a set of time intervals in which it describes the time in which it needs to be executed. A subset of intervals is said to be compatible if two-time intervals don’t overlap.

Example:-

Consider three events A, B, C need to complete in a day. Consider the time interval of event A is 1:00 to 4:00 and time interval of event B is 3:00 to 6:00 and time interval of event C is 5:00 to 8:00.

From the above example, we can conclude that events A and C are compatible because the time intervals of these two events don’t overlap. But event B is not compatible because the time interval of event B overlaps with the time intervals of events A and C.

The main aim of this algorithm is to find the largest compatible sets. That is to execute as many tasks as possible.

 Implementation of Interval Scheduling in Python

Source Code: Python

def interval_scheduling(start, finish):
    
    index = list(range(len(start)))

    max_set = set()
    prev_event_time = 0
    for i in index:
        if start[i] >= prev_event_time:
            max_set.add(i)
            prev_event_time = finish[i]
 
    return max_set
 
 
task = int(input('Enter the number of tasks: '))
start = input('Enter the start time of the tasks in order: '
              .format(task)).split()
start = [int(begin) for begin in start]
finish = input('Enter the finish times of the tasks in order: '
               .format(task)).split()
finish = [int(end) for end in finish]
 
result = interval_scheduling(start, finish)
print('Maximum number of tasks can be executed are', result)

Output:-

Case -1:-

Enter the number of tasks: 3                                                                                                                   
Enter the start time of the tasks in order: 1 5 8                                                                                              
Enter the finish times of the tasks in order: 2 8 10                                                                                           
Maximum number of tasks can be executed are {0, 1, 2}


In the above example, three tasks or events are present. The tasks are labeled as o to n-1 in the code. But in the example, the three tasks are from 0 to 2. The task 0 time interval is from 1 to 2, task 1 time interval is from 5 to 8 and task 2 time interval is from 8 to 10. Here there is no overlap of the time interval of events or tasks. So all the events or tasks are executed in this example.

Case -2:-

Enter the number of tasks: 6                                                                                                                   
Enter the start time of the tasks in order: 1 2 0 5 7 6                                                                                        
Enter the finish times of the tasks in order: 3 4 2 6 8 10                                                                                     
Maximum number of tasks can be executed are {0, 3, 4}

In the above example, there are 6 tasks labeled from 0 to 5 and the start time, end time of the tasks are also given. Here, there are overlaps of time intervals. The start time of task 1 overlap with the time interval of task 0. So all the tasks cannot be executed here.

 

You can also read,

Leave a Reply

Your email address will not be published. Required fields are marked *