Max clique in interval graph According to Efficient algorithms for interval graphs and circular arc graphs there is an $O(n \log n)$ algorithm for finding the max clique in an interval graph, assuming you have the interval model. Unfortunately, neither the paper nor the references actually elaborate on what the algorithm is, beyond saying that you can modify the well-known algorithm for optimally coloring interval graphs (where you greedily color the graph in the order generated by sorting the intervals lexicographically) to compute the max clique. This makes sense, as the largest color used in an optimal coloring is the size of the max clique in a perfect graph (and interval graphs are perfect). Unfortunately, beyond that, I am lost as to how to compute the max clique. The obvious approach is to modify some data structure every time the max color increases, but I can't figure out precisely what data structure to use or how to modify it.

Does anyone know a reference for this algorithm or can reinvent a description of it?
Interval graphs are chordal graphs, so you can use a linear time algorithm for finding max clique in a chordal graph. This can be done by first finding a perfect elimination ordering, and then using the fact that every time a vertex is eliminated it forms a clique together with its neighbors that are not eliminated yet. Furthermore all maximal cliques appear in this process. 

To find the perfect elimination ordering, maximum cardinality search (MCS) is the simplest algorithm and it works in linear time. (I don't know why Wikipedia mentions lexbfs first, it is much more complicated.)