In the art hall guarding problem we are give a line L that represents a long hallway in an art gallery. We are also given a set X = {x0, x1,..., xn-1} of real numbers that specify the positions of paintings in the hallway. Suppse that a single guard can protect all the paintings within distance of at most 1 of his or her position (on both sides). Design an algorithm for finding a placement of guards that uses the minimum number of guards to guard all the paintings with positions in X. Give the running time and prove that your algorithm is correct.

Now here's my idea: a greedy algorithm that places a guard at x1, x4, x7, ... until it all the paintings in the hall are covered. I believe this gives the minimum number of guards required to guard all the paintings, and has a linear run time, but I am guessing that there is a more elaborate answer with faster runtime... Can anybody give me tips?