Problem Description

Interval Scheduling is a class of algorithmic problems concerned with finding optimum schedules for a specific collection of tasks. That is, consider a set of tasks, each of which is represented by an interval: a tuple of starting and ending times designating the time that a "machine" would need to execute the task. In the most basic version of this problem, the goal would be to find the largest compatible subset of tasks (i.e. a schedule containing the highest number of tasks).
 
What makes this problem interesting is how easily it can be generalized into an NP-hard problem; if we just add weights to the tasks and partition them into disjoint groups, each of which can be worked on by a specific set of machines, the problem becomes impossible to solve in polynomial time (that is, if P does not equal NP).