Récursion - qu'est-ce que je fais mal?

Question

J'ai besoin de trier les valeurs de telle sorte que la liste toReturn doit contenir les éléments suivants:

Test(1100, 1130) 
Test(1134, 1200) 
Test(1210, 1310) 
Test(1100, 1140) 
Test(1145, 1210) 
Test(1220, 1320) 

Je reçois:

Test(1100, 1130) 
Test(1134, 1200) 
Test(1210, 1310) 
Test(1100, 1140) 
Test(1145, 1210) 
Test(1134, 1200) 
Test(1220, 1320) 

En fait, en boucle à travers les trois listes et vérifier si le Début de la seconde est> Fin de la première.

J'ai essayé différentes manières de résoudre ceci et ceci de la façon la plus proche que j'ai pu obtenir, mais je n'obtiens toujours pas les résultats comme je l'espère. Est-ce que quelqu'un peut s'il vous plaît aviser ce que je pourrais faire mal?

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace ConsoleApplication22 
{ 
    class Program 
    { 
     static List<Test> toReturn = new List<Test>(); 

     static void Main(string[] args) 
     { 
      List<Test> l1 = new List<Test>(); 
      l1.Add(new Test(1100, 1130)); 
      l1.Add(new Test(1100, 1140)); 
      l1.Add(new Test(1110, 1150)); 

      List<Test> l2 = new List<Test>(); 
      l2.Add(new Test(1134, 1200)); 
      l2.Add(new Test(1145, 1210)); 

      List<Test> l3 = new List<Test>(); 
      l3.Add(new Test(1210, 1310)); 
      l3.Add(new Test(1220, 1320)); 

      List<List<Test>> container = new List<List<Test>>(); 
      container.Add(l1); 
      container.Add(l2); 
      container.Add(l3); 

      sort(container, 0, 0); 
     } 

     private static void sort(List<List<Test>> temp, int position, int time) 
     { 
      if (position + 1 == temp.Count) 
      { 
       return; 
      } 

      List<Test> tt = temp[position]; 

      if (position + 1 < temp.Count) 
      { 
       List<Test> tt1 = temp[position + 1]; 

       for (int i = 0; i < tt.Count; i++) 
       { 
        int t1 = tt[i].End; 

        for (int j = 0; j < tt1.Count; j++) 
        { 
         int t2 = tt1[j].Start; 

         if (t2 > t1 && t2 > time) 
         { 
          //if (toReturn.Count == 0) 
          //{ 
          if (toReturn.Count == 0) 
          { 
           toReturn.Add(tt[i]); 
          } 
          else 
          { 
           if (toReturn[toReturn.Count - 1].End != tt[i].End && toReturn[toReturn.Count - 1].Start != tt[i].Start) 
           { 
            toReturn.Add(tt[i]); 
           } 
          } 

          if (toReturn[toReturn.Count - 1].End != tt1[j].End && toReturn[toReturn.Count - 1].Start != tt1[j].Start) 
          { 
           toReturn.Add(tt1[j]); 
          } 

          sort(temp, position + 1, tt1[j].End); 
          break; 
         } 
        } 

        if (position > 0) 
        { 
         return; 
        } 
       } 
      } 
      String val = ""; 
      //return toReturn; 
     } 
    } 

    class Test 
    { 
     int start; 

     public Test(int val1, int val2) 
     { 
      Start = val1; 
      End = val2; 
     } 

     public int Start 
     { 
      get { return start; } 
      set { start = value; } 
     } 

     int end; 

     public int End 
     { 
      get { return end; } 
      set { end = value; } 
     } 
    } 
} 

Answer 1

Utilisez un comparateur, comme le suggère: Un élément est inférieur à un autre si son extrémité est inférieure début de l'autre. Un élément est supérieur à un autre si son début est supérieur à la fin de l'autre.

class TestComparer : IComparer<Test> 
{ 
    int Compare(Test a, Test b) 
    { 
     if (a.End < b.Start) return -1; 
     else if (a.Start > b.End) return 1; 
     else return 0; 
    } 
} 
... 
List.Sort(list, new TestComparer()); 

Modifier après avoir relu votre question, je suivrais une approche comme celle ci-dessous:

• Bien qu'il y ait un élément gauche dans la liste
• élément Rechercher avec le plus petit début
  • Ajouter à la liste qui en résulte, et le retirer de la liste
  • Alors qu'un élément avec un lar ger Démarrer puis la dernière fin de l'élément dans la liste résultant existe
    • Ajouter à la liste des résultats, et le retirer de la liste

Quelque chose comme:

while (list.Count > 0) 
{ 
    int i = GetSmallestTestIdx(list); 
    do 
    { 
     result.Add(list[i]); 
     list.RemoveAt(i); 
    } 
    while ((i = GetNextTextIdx(list, result)) != -1); 
}