Recursion - what am I doing wrong?

Question

I need to sort out the values in such a way that the toReturn list should contain the following:

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

I get:

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

Basically, looping through the three lists and checking if the Start of second is > End of first.

I have tried various ways to solve this and this the closest I could get, but still don't get the results as I expect.

Can someone please advise what I might be doing wrong?

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

Use a comparator, as suggested: An element is less than another if its End is less than the other's Start. An element is greater than another if its Start is greater than the other's End.

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());

Edit After re-reading your question, I would follow an approach like the one below:

• While there is an element left in the list
• Find element with smallest Start
  • Add it to the resulting list, and remove it from the list
  • While an element with a larger Start then the last item's End in the resulting list exists
    • Add it to the resulting list, and remove it from the list

Something like:

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