Vai al contenuto principale

Informatica · Greedy

Minimo di frecce per 5 palloncini, l'ultimo fra 1 e 5

Ci sono 5 palloncini, ognuno che occupa l'intervallo orizzontale [1,2], [2,3], [3,4], [4,5], [1,5]. Una freccia tirata in verticale a una certa posizione fa scoppiare tutti i palloncini il cui intervallo contiene quella posizione. Qual è il minimo numero di frecce necessarie per far scoppiare tutti i palloncini?