An interval graph is a graph whose vertices can be represented by intervals on a line, with two vertices adjacent exactly when their intervals intersect. For example, intervals represent a single edge and an isolated vertex.
Interpreting an interval as the duration of a task makes an edge mean that the tasks overlap. A proper vertex coloring then assigns resources so simultaneous tasks use different resources. For interval graphs, the minimum number of colors equals the largest number of mutually overlapping intervals, their clique number. Sorting endpoints provides an efficient way to recognize and exploit this structure.
New to topics? Read the docs here!