Algorithme pour trouver la somme maximale dans une séquence d'intervalles de chevauchement

Le problème que j'essaie de résoudre a une liste d'intervalles sur la ligne numérique, chacun avec un score prédéfini. Je dois retourner le score total maximum possible.

Le hic est que les intervalles se chevauchent, et des intervalles qui se chevauchent, Je ne peux en utiliser qu'un seul. Ici est un exemple. 

Intervals   - Score  
   0- 5     -  15  
   4- 9     -  18  
  10-15     -  12  
   8-21     -  19  
  25-30     -  25

Ici, les intervalles 0-5, 4-9 et 8-21 se chevauchent.
Les intervalles 10-15 et 8-21 se chevauchent également.
La somme maximale serait de 55 (18+12+25).

, Il est important de noter ici que nous sélectionnons l'intervalle 4-9 du premier lot d'intervalles de chevauchement même s'il n'a pas le score le plus élevé des trois.

C'est parce que la sélection de l'intervalle 8-21 nous empêcherait d'utiliser l'intervalle 10-15 plus tard, réduisant ainsi la somme globale (dans ce cas, la somme globale serait 19+25=44).

Je cherche une solution O(nlogn) ou O(n) à ce problème. Je pense que la programmation dynamique peut être utilisée, mais je peux me tromper. Quelqu'un pourrait-il suggérer une solution/algorithme(s) qui pourrait faire l'affaire ici?

Edit: les intervalles ne sont pas dans un ordre particulier.

22
demandé sur Bakuriu 2010-07-14 07:35:06

6 réponses

C'est pondérée de la variation de intervalle de planification; il est soluble dans O(N log N) avec programmation dynamique.

Laissez un intervalle être g(start, stop, score), et laissez-les être triés par stop. Pour simplifier, supposons pour l'instant que all stop est unique.

Laissez - best[i] soit le meilleur score, nous pouvons obtenir lorsque nous sommes autorisés à utiliser g[1], ..., g[i]. Nous n'avons pas à les utiliser tous, bien sûr, et généralement nous ne pouvons pas parce que le sous-ensemble d'intervalles que nous utilisons doivent être non-cumul.

  • Clairement best[0] = 0. Autrement dit, Puisque nous ne pouvons utiliser aucun intervalle, le meilleur score que nous pouvons obtenir est 0.
  • Pour tout 1 <= k <= N, nous avons:
    • best[k] = max( best[k-1], best[j] + g[k].score ), où
      • j est le plus grand indice tel que g[j].stop < g[k].start (j peut être zéro)

C'est-à-dire, étant donné que nous sommes autorisés à utiliser g[1], ... g[k], le mieux que nous pouvons faire est la meilleure notation de ces deux options:

  • , Nous n'incluons pas g[k]. Ainsi, le score de cette l'option est best[k-1].
    • ... parce que c'est le mieux que nous pouvons faire avec g[1], ... g[k-1]
  • Nous incluons g[k], et à sa gauche nous faisons de notre mieux avec tous les gènes qui ne se chevauchent pas avec g[k], c'est-à-dire tout g[1], ..., g[j], où g[j].stop < g[k].start et j est aussi grand que possible. Ainsi, le score de cette option est best[j] + g[k].score.

(notez la sous-structure optimale et les composants de sous-problèmes qui se chevauchent de la programmation dynamique incorporés dans l'équation ci-dessus).

L'ensemble réponse à la question est best[N], c'est à dire le meilleur score, nous pouvons obtenir lorsque nous sommes autorisés à utiliser tous les gènes. Oups, ai-je dit de gènes? Je veux dire les intervalles.

C'est O(N log N) parce que:

  • trier tous les intervalles prend O(N log N)
  • Trouver j pour chaque k est O(log N) à l'aide de la recherche binaire

Si plusieurs gènes peuvent avoir les mêmes valeurs stop, alors rien n'a changé: vous devez toujours chercher le j le plus à droite. Dans Par exemple Python c'est facile avec bisect_right. En Java, où la recherche binaire de la bibliothèque standard ne garantit pas quel index est retourné en cas de liens, vous pouvez (parmi de nombreuses options) le suivre avec une recherche linéaire (pour O(N) les performances les plus défavorables), ou une autre série de recherches binaires pour trouver l'index le plus juste.

Oups ai-je encore dit gènes? Je veux dire les intervalles.

Questions connexes

23
répondu polygenelubricants 2017-05-23 12:31:55

Tout d'abord, je pense que le maximum est 59, pas 55. Si vous choisissez intervalles [0-5], [8-21] et [25,30], vous obtenez 15+19+25 = 59. Vous pouvez utiliser une sorte de programmation dynamique pour gérer cela.

Tout d'abord, vous triez tous les intervalles par leur point de départ, puis itérez de fin en début. Pour chaque élément de la liste, vous choisissez la somme maximale de ce point à la dernière comme max(S[i]+S[j], S[i+1]), Où i est l'élément que vous êtes sur, j est l'élément qui est la première entrée qui ne se chevauchent pas après votre élément (c'est-à-dire, le premier élément dont le début est plus grand que la fin de l'élément en cours). Pour accélérer l'algorithme, vous voulez stocker la somme partielle maximale S [j] pour chaque élément.

Pour clarifier, permettez-moi de résoudre votre exemple en fonction de ceci. Tout d'abord, triez vos intervalles: 

 1:  0- 5 -  15
 2:  4- 9 -  18
 3:  8-21 -  19
 4: 10-15 -  12
 5: 25-30 -  25

Donc,

 S[5] = 25
 S[4] = max(12+S[5], 25)=37
 S[3] = max(19+S[5], S[4])=max(19+25,37)=44
 S[2] = max(18+S[4], S[3])=max(18+37,44)=55
 S[1] = max(15+S[3], S[2])=max(15+44, 55)=59

C'est une adaptation de l'algorithme dans ce post , mais malheureusement, n'a pas le bon temps D'exécution O(n). Une liste dégénérée où chaque entrée chevauche la suivante le ferait être O (n^2).

4
répondu vhallac 2017-05-23 12:09:32

Peut-être une approche comme dans cette réponse peut être utilisé, qui est O(n), au moins pour ce problème. Cela signifierait itérer une fois à travers les intervalles et garder une trace de seulement ces combinaisons d'intervalles qui pourraient encore conduire à une solution finale optimale.

0
répondu sth 2017-05-23 12:17:21

Ressemble à une variation sur le problème du sac à dos. Vous pourriez trouver de l'inspiration dans la recherche de ces solutions.

Combien d'intervalles parlons-nous? Si ce n'est que 5 (comme dans votre exemple), il est probablement plus pratique d'essayer toutes les combinaisons. Si c'est plus une approximation d'une solution idéale faire? Encore une fois, les solutions de Sac À Dos (telles que L'algorithme d'approximation gourmande de George Dantzig) pourraient être un bon point de départ.

0
répondu Damovisa 2010-07-14 03:52:21

J'y ai pensé un peu et j'ai trouvé quelque chose.

Les Arbres D'intervalle fournissent un moyen efficace de trouver tous les intervalles qui chevauchent un intervalle donné. En parcourant l'ensemble des intervalles, nous pouvons trouver tous les intervalles qui se chevauchent pour un intervalle donné. Une fois que nous avons, nous pouvons trouver l'intervalle avec le score le plus élevé, de stocker et d'avancer.

La construction de l'arbre prend du temps O (N Log n) et la recherche prend du temps O(Log n). Parce que nous faisons une recherche pour tous éléments, la solution devient O (N Log n).

Cependant, si nous faisons face à quelque chose comme l'exemple ci-dessus où l'intervalle de score le plus élevé dans un groupe réduit le total, l'algorithme échoue parce que nous n'avons aucun moyen de savoir que l'intervalle de score le plus élevé ne doit pas être utilisé avant la main. La manière évidente de contourner cela serait de calculer les deux (ou tous) totaux au cas où nous ne sommes pas sûrs,mais cela nous ramène à une solution potentiellement O (N^2) ou pire.

0
répondu efficiencyIsBliss 2010-07-14 15:39:06

Je pense que nous pouvons utiliser cette récursivité...

S[i] indique le score de chaque intervalle
Interval[i] désigne tous les intervalles

ResMax[i] = max(ResMax[i-1] + S[i] //if i is included
           ,max(R[i-1],S[i]) 
         )

Je ne suis pas vérifié à fond, mais il devrait fonctionner je crois.

0
répondu Jyotirmoy Sundi 2011-11-23 04:50:44