Consider the following problem. The input is a set A = {a1, a2, , an} of n points on the real line. The problem is to find a minimum cardinality set S of unit intervals that cover every point in A. (Note that the interval does not need to start at interger points, it only needs to be of unit length, that is, a valid interval is of form [x, z+1] for any real value x. Another way to think about this same problem is the following. You know a set of times A that trains will arrive at a station. When a train arrives there must be someone manning the station. Due to union rules, each employee can work at most one hour at the station. The problem is to find a scheduling of employees that covers all the times in A and uses the fewest number of employees. a Consider the following algorithm: Initialize SD, and A is initially the set of points to be covered i Let I be an interval that covers the most number of points in A ii Add I to the solution set S, and remove those points covered by I from A iii If A is empty, return S. Otherwise, continue to Step (i) Consider the following problem. The input is a set A = {a1, a2, , an} of n points on the real line. The problem is to find a minimum cardinality set S of unit intervals that cover every point in A. (Note that the interval does not need to start at interger points, it only needs to be of unit length, that is, a valid interval is of form [x, z+1] for any real value x. Another way to think about this same problem is the following. You know a set of times A that trains will arrive at a station. When a train arrives there must be someone manning the station. Due to union rules, each employee can work at most one hour at the station. The problem is to find a scheduling of employees that covers all the times in A and uses the fewest number of employees. a Consider the following algorithm: Initialize SD, and A is initially the set of points to be covered i Let I be an interval that covers the most number of points in A ii Add I to the solution set S, and remove those points covered by I from A iii If A is empty, return S. Otherwise, continue to Step (i)