Vai al contenuto principale

Informatica · Greedy

Minimo di frecce per 6 palloncini, l'ultimo fra 15 e 20

Ci sono 6 palloncini, ognuno che occupa l'intervallo orizzontale [10,16], [2,8], [1,6], [7,12], [11,22], [15,20]. 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?