1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86
| class Manteau
{
// Si on range directement les Elements dans cette liste triés selon min puis max croissants, ca permet de ne pas avoir à la parcourir.
List<Manteau> fils = new ArrayList<Manteau>();
int min;
int max;
Manteau(int min, int max)
{
this.min = min;
this.max = max;
}
void addManteau(Manteau manteau)
{
int i = 0;
while(i < fils.size() && manteau.min >= fils.get(i).min)
{
if(manteau.max <= fils.get(i).max)
{
fils.get(i).addManteau(manteau);
return;
}
++i;
}
// i pointe sur le premier manteau dont le min est plus grand ou bien sur fils.size()
// Maintenant, on regarde si un ou plusieurs manteaux peuvent etre inclus dans le nouveau manteau
while(i < fils.size() && manteau.max >= fils.get(i).max)
{
// Tous les manteaux ici devront etre supprimes de l'element pere (this) et inseres dans le nouvel element
// Note qu'ici, on peut inserer directement la liste sans avoir a faire les verifications de addManteau (puisqu'elles ont deja ete faites)
manteau.addManteau(fils.get(i));
fils.remove(i);
}
fils.add(i, manteau);
}
int compteFils()
{
int ret = fils.size();
for(Manteau manteau : fils)
{
ret += manteau.compteFils();
}
return ret;
}
@Override
public String toString()
{
return "[" + min + "," + max + "]";
}
}
Manteau base = new Manteau(0, 0);
Manteau el;
ArrayList<Manteau> listManteaux = new ArrayList<Manteau>();
el = new Manteau(1, 3);
base.addManteau(el);
listManteaux.add(el);
el = new Manteau(2, 5);
base.addManteau(el);
listManteaux.add(el);
el = new Manteau(5, 8);
base.addManteau(el);
listManteaux.add(el);
el = new Manteau(3, 6);
base.addManteau(el);
listManteaux.add(el);
el = new Manteau(2, 5);
base.addManteau(el);
listManteaux.add(el);
el = new Manteau(3, 8);
base.addManteau(el);
listManteaux.add(el);
el = new Manteau(3, 6);
base.addManteau(el);
listManteaux.add(el);
el = new Manteau(3, 8);
base.addManteau(el);
listManteaux.add(el);
for(Manteau manteau : listManteaux)
{
System.out.println("Manteau " + manteau.toString() + " fils=" + manteau.compteFils());
} |
Partager