Interval covering P37902


Statement
 

pdf   zip

html

Given several real numbers x1, …, xn, we want to find the smallest possible set of closed intervals of length 1 that cover those real numbers. In other words, we must find a set of intervals {[y1, y1 + 1], …, [ym, ym + 1]} such that

  • for every xi, there exists some j such that xi ∈ [yj, yj + 1];
  • m is minimum.

For instance, if the xi’s are 1.4, 1.9, 2.3 i 2.7, a possible solution is {[1.2, 2.2], [1.8, 2.8]}, because every xi is inside of (at least) one of the two intervals, and it is not possible to cover the four real numbers with only one interval.

Input

Input consists of several cases, each with a number n followed by n different real numbers. Assume n ≤ 105.

Output

For every case, print the minimum number of closed intervals of length 1 that cover the given real numbers.

Public test cases
  • Input

    4  1.4 1.9 2.3 2.7
    6  1.75 3.5 0.5 3 1.5 0.2
    2  -2.5 -3.5
    

    Output

    2
    3
    1
    
  • Information
    Author
    Amalia Duch
    Language
    English
    Translator
    Amalia Duch
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++