Q:

How to prove the optimality of this greedy algo?

Given N integers. Each of these numbers can be increased or decreased once by no more than given positive integer L. After each operation if any numbers become equal we consider them as one number. The problem is to calculate cardinality of minimal set of distinct integers.
Constraints: N <= 100, L <= 3200, integers are in the range [-32000, 32000]
Example: 
N = 3, L = 10
11 21 27
1) increase 11 by 10 => 21 21 27
2) decrease 27 by 6 => 21 21 21
The answer is 1.
Algo in C++ language:
    sort(v.begin(), v.end());
    // the algo tries to include elements in interval of length 2 * L
    int ans = 0;
    int first = 0; 
    for(int i = 1; i < N; ++i) {
        if(v[i] - v[first] > 2 * L) { // if we can't include i-th element 
            ans++;                    // into the current interval   
            first = i;                // the algo construct new 
        }
    }
    ans++;
    printf("%d", ans);

I try to understand why this greedy algo is optimal. Any help is appreciated.

A:

Let $I_1, \ldots, I_k$ denote the intervals that your algorithm computes, i.e. all $v[i]$ which fulfill $v[i] - v[\mathrm{first}] \leq 2 L$ for a value of first belong to the same interval. Similalry, let $J_1, \ldots, J_{k'}$ denote the intervals that an optimal algorithm would choose. Since your algorithm computes a feasile solution comparing it with the optimal oslution yields $k' \leq k$.
Without loss of generality we assume that the intervals are non-decreasingly sorted. Then $v[0] \in I_1$ and $v[0] \in J_1$. Since your algorithm chooses $\max(I_1)$ as large as possible, it must hold that $\max(I_1) \geq \max(J_1)$. Thus, $\min(I_2) \geq \min(J_2)$. Since $I_2$ was again chosen such that $\max(I_2)$ is maximal, either $\max(I_2)$ is contained in $J_2$ which implies $\max(I_2) = \max(J_2)$, or it is not contained which implies $\max(I_2) > \max(J_2)$. So we get again $\max(I_2) \geq \max(J_2)$.
This argument can be inductively repeated to show that $\max(I_k) \geq \max(J_k)$. Since the $I_1, \ldots, I_k$ cover your list, the sets $J_1, \ldots, J_k$ will also cover the list. Thus, $k = k'$ and the optimal number of intervals to cover the list is $k$ which is the result of your algorithm.

