Annettuna on lista, jonka jokainen alkio on eri kokonaisluku. Tehtäväsi on esittää listan sisältö lukuväleinä niin, että välien määrä on mahdollisimman pieni. Lukuväli $[a,b]$ tarkoittaa, että listalla ovat kaikki luvut väliltä $a \dots b$.

Esimerkiksi lista $[5,2,7,6,3,9]$ voidaan esittää kolmena lukuvälinä: $[2,3]$, $[5,7]$ ja $[9,9]$.

Voit olettaa, että listan jokainen alkio on kokonaisluku välillä $1 \dots 10^9$ ja listalla on enintään $10^5$ alkiota.

Python

Toteuta tiedostoon intervals.py funktio count, joka ilmoittaa välien määrän.

def count(t):
    # TODO

if __name__ == "__main__":
    print(count([4,1,5,3])) # 2
    print(count([4,2,1,3])) # 1
    print(count([5,2,7,6,3,9])) # 3

Java

Toteuta tiedostoon Intervals.java metodi count, joka ilmoittaa välien määrän.

public class Intervals {
    public int count(int[] t) {
        // TODO
    }

    public static void main(String[] args) {
        Intervals i = new Intervals();
        System.out.println(i.count(new int[] {4,1,5,3})); // 2
        System.out.println(i.count(new int[] {4,2,1,3})); // 1
        System.out.println(i.count(new int[] {5,2,7,6,3,9})); // 3
    }
}