Related Problems: graph-coloring Type: Constructive algorithm Work on: Graph

First Fit algorithm is the easiest and fastest technique of all greedy coloring heuristics. The algorithm sequentially assigns each vertex the lowest legal color. This algorithm has the advantage of being very simple and fast and can be implemented to run in O(n)

Algorithm: allocate the lowest color to the current interval that respects the constraints imposed by the intervals that have been colored. Formally, a coloring of a set of intervals by a function h defined on the set of intervals.
In other-words, an interval I is said to be assigned a color h(I) which is a positive integer.
In the coloring obtained by applying the First-Fit algorithm, if an interval I is assigned a color h(I), then for all colors 1 ≤ i < h(I), there exists an interval I such that I ∩ I = φ and h(I) = i.
The simplicity of First-Fit has made it one of the main choices for the purpose.

References: New Graph Coloring Algorithms by Dr. Hussein Al-Omari and Khair Eddin Sabri ,
A Note on First-Fit Coloring of Interval Graphs