Cobrint intervals P37902

Donats diversos reals x₁, …, 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₁, y₁ + 1], …, [y_m, y_m + 1]} tal que

• per a cada x_i, existeixi alguna j tal que x_i ∈ [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 ≤ 10⁵.

Sortida

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