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. When none of the intervals overlap the optimum solution is trivial. However, when multiple tasks are overlapping, the problem gets more difficult. One typical way to evaluate a solution is to measure the number of tasks that are completed. This problem can be solved with the greedy algorithm earliest deadline first scheduling. Note that multiple optimal solutions may exist.
In the case of weighted intervals greedy algorithms fail, dynamic programming can solve such interval scheduling.
[edit] See also
[edit] Sources
- Kleinberg, Jon; Tardos, Eva (2006). Algorithm Design. ISBN 0-321-29535-8.
