Let $G$ be an interval graph and take one of its vertices $x$. Can we find in linear time a minimum number of vertex disjoint paths of $G$ which cover the vertex set of $G$ and have $x$ as one of their endpoints? This paper provides a positive answer to this problem. In the course of developing such an algorithm, we explore the possibility of getting insight on the path structure of interval graphs via greedy graph searches.