Unit-Length Closed Intervals

I am working on a program that has somewhat focus on the below:

unit-length closed interval on the real line is an interval [x, 1+x]. For given input set

X={x1,x2,..., Xn}, x1 < x2 <...xn, how c开发者_如何学Goan i determine the smallest set of unit-lenght closed intervals that contains all of the given points and how i calculate time complexity.

I dont need code but an algorithm to set up my program correctly will just do fine

Thanks

Your points are sorted in increasing order. We can solve this by greedy approach. Make the first interval start at x1. Then set the second interval start with the first points out of the first interval. So on.

Since its an instance of a set-cover problem, a polynomial time algorithm is unlikely to beat a greedy solution by much. So you could try placing unit intervals that cover the most number of yet uncovered points. For the position of the intervals you dont lose by aligning it with some data point in X.

Greedy: The time complexity is O(n), maximun. Like x1<...