Minimisation le nombre de boîtes qui couvrent un ensemble d'intervalles

Question

c'est une question pour les gourous algorithmes là-bas :-)

Soit S un ensemble d'intervalles des nombres naturels qui pourraient se chevaucher et b une boîte Taille. Supposons que pour chaque intervalle, la plage est strictement inférieure à b.

Je veux trouver l'ensemble minimal d'intervalles de taille b (appelons-le M) de sorte que tous les intervalles dans S sont contenus dans les intervalles de M.

exemple Trivial:

S = {[1..4], [2..7], [3..5], [8..15], [9..13]} 
b = 10 
M = {[1..10], [8..18]} 
// so ([1..4], [2..7], [3..5]) are inside [1..10] and ([8..15], [9..13]) are inside [8..18] 

Je pense qu'un algorithme glouton peut ne pas fonctionner toujours, donc si quelqu'un sait d'une solution à ce problème (ou similaire qui peut être converti en), ce serait génial .

Merci! J'ai réfléchi un peu plus à ce sujet, et peut-être que ma première intuition était fausse et qu'un algorithme glouton est juste la façon de résoudre cela, car à la fin tous les intervalles doivent être couverts et cela ne ferait aucune différence comment les super-intervalles sont choisis ... Dois-je supprimer la question ou peut-être quelqu'un peut affirmer cela?

Answer 1

L'algorithme peut être le suivant.

1. a = 0
2. curr = nombre le plus bas en S qui est> a. (Dans notre cas = 1. dans [1..4])
3. Ajouter un intervalle [curr..b] à M. (Dans notre cas M = {[1..10]})
4. a = max supérieure liée à M. (dans notre cas a = 10)
5. Aller à 2.

Answer 2

Oui, l'algorithme glouton est optimal. Informellement, considérons une solution arbitraire M. Nous allons le transformer en un surensemble de la solution gloutonne M 'sans augmenter le nombre d'intervalles. Considérons à plusieurs reprises l'intervalle le plus à gauche I dans M - M '. Soit s l'intervalle le plus à gauche dans S pour lequel I est l'intervalle le plus à gauche dans M pour contenir s. L'algorithme glouton de gauche à droite choisit un intervalle I 'dont le bord gauche est aligné avec s. Je prétends d'abord que je suis à la droite de I, puisque I 'est l'intervalle le plus à droite pour contenir s, et deuxièmement, que M - {I} U {I'} est une solution valide, puisque les seuls intervalles contenus par I mais non je suis à gauche de s et donc déjà contenue par un autre intervalle. Le nombre d'intervalles qui ne sont pas dans la solution gourmande diminue, donc nous finissons par atteindre la solution gourmande.