How to design a traffic control scheme for a long highway of length $L$? We have $n$ possible control teams; team \# $i$ can effectively control traffic on an interval $[a^-_i,a^+_i]$, and the cost of this team's use is $c_i$. We must select the teams so that the entire highway is covered, and the total cost is the smallest possible.
Similar problems emerge:
in {\it scheduling}; e.g., if we schedule the teaching assistants to supervise a computer lab;
in {\it biology}, where, e.g., we must decode the DNA in the cheapest possible way by decoding its segments $[a^-_i,a^+_i]$;
in {\it VLSI design}, where we must find the cheapest set of tests that covers the entire path of the signal;
and in many other application areas.
The traditional way to solve this problem is to design a graph whose nodes are intervals ${\bf a}$, ${\bf b}$, ..., and in which $\bf a$ and $\bf b$ are connected iff ${\bf a}\cap {\bf b}\ne\emptyset$. Such a graph is called a ({\it weighted}) {\it interval graph}, and the problem is reduced to finding a shortest path in this graph.
Traditional shortest path algorithms require time that is quadratic in the size $n$ of the input. In this paper, a new {\it linear time} algorithm is proposed. (To be more precise, this algorithm requires linear time if we assume that the set of all endpoints $a^\pm_i$ is already ordered; otherwise, it takes time $O(n\log(n))$.)
In many real-life problems, we have a similar problem: we have {\it arcs} on a {\it circle}, and we must find the cheapest set of arcs that covers the entire circle. For example, in traffic control, the road may be a loop. For this problem, the authors propose a quadratic-time algorithm.