URL: https://linuxfr.org/forums/programmationautre/posts/algorithmie-aire-la-plus-grande-de-blocs-se-superposant Title: [Algorithmie] Aire la plus grande de blocs se superposant Authors: steckdenis Date: 2010年01月14日T14:58:18+01:00 Tags: Score: 4 Bonjour, Dans le cadre d'un projet visant à créer un algorithme de différences binaires, j'ai besoin de votre aide pour m'aider dans une de ces étapes de cet algorithme. Avant toute chose, je tiens à préciser que je ne peux pas réutiliser l'existant, comme bsdiff, xdelta3, voire même tout ce qui est zlib, bzip2, etc. Pour illustrer mon problème, voici une [image](http://www.logram-project.org/files/uploads/2010/01/14/135636/rects.png) représentant la chose. La ligne du dessus représente une suite de rectangles, qui commencent tous à un certain caractère et ont une certaine taille, positive et non-nulle. La ligne du dessous représente le résultat que je veux obtenir. Le but est, parmi les rectangles de la ligne du dessus, de trouver la suite des rectangles qui ne se chevauchent pas, et qui forment la plus grande surface (longueur totale la plus importante). La difficulté étant de trouver ces rectangles, et rapidement (il y en aura des milliers dans l'application finale). Il est capital que la somme de la taille des rectangles trouvés soit la plus importante. Il serait aussi excellent que les rectangles trouvés soient dans l'ordre (donc d'abord celui qui commence le plus à droite, puis le suivant, etc). Notez que je ne vous demande nullement de faire un de mes devoirs à ma place. Ce problème n'est pas universitaire, il ne vient pas d'un éventuel travail. Non, il servira à implémenter un algorithme de diff binaire dans mon gestionnaire de paquets Setup. Pourquoi ne pas réutiliser bsdiff ? Parce que une fois ce problème de rectangles résolu, l'algorithme produira des différences bien plus petites. Une fois cette dernière pièce du puzzle rassemblée, le résultat sera bien entendu disponible dans Setup, ainsi que dans une application C pur, libre bien entendu, à part. Je publierai également le détail de l'algorithme utilisé. Vous pouvez demander pour avoir votre nom cité dedans. Bien évidemment, aucun brevet logiciel ne sera déposé dessus, et le nécessaire sera fait pour qu'il n'y en ai jamais. Merci d'avance :-) .