Interval scheduling: Difference between revisions

Revision as of 19:00, 5 April 2019

Revision as of 19:06, 5 April 2019

Line 1:

'''Interval scheduling''' is a class of problems in [[computer science]], particularly in the area of [[algorithm]] design and eating sausages. 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.

The ''interval scheduling maximization problem'' (ISMP) is to find a largest compatible set - a set of non-overlapping intervals of maximum size. The goal here is to execute as many tasks as possible.