Cobrint intervals P37902

Donats diversos reals $x_1, \ldots, x_n$, es vol trobar el conjunt més petit possible d’intervals tancats de mida 1 que cobreixin aquests reals. En altres paraules, cal trobar un conjunt d’intervals $\{[y_1, y_1 + 1], \dots, [y_m, y_m + 1]\}$ tal que

• per a cada $x_i$, existeixi alguna $j$ tal que $x_i \in [y_j, y_j + 1]$;

• la $m$ sigui mínima.

Per exemple, si les $x_i$’s són $1.4, 1.9, 2.3$ i $2.7$, una possible solució és $\{[1.2, 2.2], [1.8, 2.8]\}$, ja que cada $x_i$ es troba (com a mínim) dins d’un dels dos intervals, i no és possible cobrir els quatre reals amb un sol interval.

Entrada

L’entrada consisteix en diversos casos, cadascun dels quals amb un nombre $n$ seguit de $n$ reals diferents. Assumiu $n \le 10^5$.

Sortida

Per a cada cas, escriviu el nombre mínim d’intervals tancats de mida 1 que cobreixin els reals donats.