Interval Scheduling.

What is the concept of Interval Scheduling?

Interval scheduling is a class of problems in computer science, particularly in the area of algorithm design. The problems consider a set of tasks. Each task is represented by an interval describing the time in which it needs to be executed. For instance, task A might run from 2:00 to 5:00, task B might run from 4:00 to 10:00 and task C might run from 9:00 to 11:00. A subset of intervals is compatible if no two intervals overlap. For example, the subset {A,C} is compatible, as is the subset {B}; but neither {A,B} nor {B,C} are compatible subsets, because the corresponding intervals within each subset overlap.

You can take help of following links :-

Example: Given 3 requests with s(1) = 1, f(1) = 3, s(2) = 2, f(2) = 4, s(3) = 3, f(3) = 5, the maximum-size subset of compatible requests is {1, 3}.

This problem can be solved optimally with a simple greedy strategy of scheduling requests based on earliest finish time i.e., from the set of compatible requests, we always select the one with the earliest finish time. The idea is to free the resource as soon as possible while still satisfying one request so as to maximize the time left to satisfy other requests.

Algorithm:

Let R be the set of all requests
schedule = {}
while !R.empty():
Choose a request i ∈ R that has the smallest finish time
Add i to schedule
Delete all requests from R that are incompatible with i
return schedule
2 Likes

is activity selection problem and Interval scheduling are same???

I think interval scheduling is an application of activity selection. Please correct me if I am wrong.

I think so…but i am not sure…