Let P = {p1, p2, · · · , pn} be a set of points on the x axis with each point pi , 1 ≤ i ≤ n, represented by its coordinates. Design a greedy algorithm to find a minimum number of intervals with unit length on the x axis to cover the set of points in P, where a point pi is covered by an interval if its x coordinate falls in the interval. For each interval you need to determine its position (i.e., its starting and ending points). Prove the correctness of your algorithm. Now suppose that the points in P are located on a 2D plane and each interval becomes an axis-aligned unit square. Prove or disprove whether your greedy strategy for the 1-D case can still be extended to the 2-D case. For proving it works, you need to clear state how the greedy strategy is extended to 2D and prove its correctness. For disproving it, you just need to give a counter example.
