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 } }