Interval scheduling

From Wikipedia, the free encyclopedia

Interval scheduling is a class of problems in computer science, particularly in the area of algorithm design. A list of tasks is given as a set of time intervals; for instance, one task might run from 2:00 to 5:00 and another task might run from 6:00 to 8:00. Posed as an optimization problem, the goal is to maximize the number of executed tasks. Weighted interval scheduling is a generalization where a value is assigned to each executed task and the goal is to maximize the total value. The solution need not be unique.

When none of the intervals overlap the optimum solution is trivial. The optimum for the non-weighted version can found with the greedy algorithm earliest deadline first scheduling. The general case requires dynamic programming.