Trovare il numero minimo di punti che copre l'intero set di intervalli?

Question

Dato un intervallo di intervalli [x,y] where 0 <= x,y <= 2000 come trovare il numero minimo di punti che possono coprire (vale a dire che ogni intervallo deve contenere almeno un punto nel set di punti risultante) tutti gli intervalli?

esempio:

Given Set of intervals: 
    [2,5] 
    [3,7] 
    [7,10] 

poi risposta dovrebbe essere 2 (numero minimo di punti necessari per coprire tutti gli intervalli) come punti x=3,x=7 è una soluzione.

Answer 1

È possibile utilizzare un algoritmo greedy:

1. Ordina tutti gli intervalli dai loro punti finali (in ordine crescente).

2. Iterare su una serie ordinata di intervalli. Quando un intervallo è finito, ci sono due opzioni:

   1. È già coperto da qualche punto. Niente dovrebbe essere fatto in questo caso.
   2. Non è ancora coperto. Quindi il punto finale di questo intervallo dovrebbe essere inserito nel set risultante.

L'insieme risultante generato da questo algoritmo è ottimale.