Give a pseudocode for Interval Partitioning Algorithm Give a

Solution

Interval partitioning problem :
Suppose there is a set {1, 2, …, n} of n requests, where i^th request starts at time s(i) and finishes at time f(i), find the minimum number of resources needed to schedule all requests so that no two requests are assigned to the same resource at the same time.

The requests i and j may conflict in one of two ways:

This problem is solved optimally with a greedy method of scheduling requests. Based on earliest start time i.e. from the set of remaining requests, we will always select the one with the earliest start time and assign it to one of the available resources or demand another resource for the request.

PseudoCode or Algorithm to implement above problem:

Let X be the set of all requests
Let r = 0 be the number of resources available
while !X.empty(): // it is used to check the request set is empty or not
Choose a request i X that has the earliest start time
if \'i\' can be assigned to some resource k <= r:
    assign request \'i\' to resource k
else
    allocate a new resource r+1
    assign request \'i\' to resource r+1
    r= r + 1
return r