递归,我哪里做错了

本文关键字:错了 递归 | 更新日期: 2023-09-27 18:16:36

我需要对这些值进行排序,使toReturn列表包含以下内容:

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

:

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

基本上,循环遍历三个列表并检查second的Start是否> End of first。

我已经尝试了各种方法来解决这个问题,这是我能得到的最接近的,但仍然没有得到我期望的结果。

谁能告诉我我可能做错了什么?
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; }
        }
    }
}

递归,我哪里做错了

按照建议使用比较器:如果一个元素的End小于另一个元素的Start,则该元素小于另一个元素。如果一个元素的Start大于另一个元素的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());

编辑重读你的问题后,我会遵循下面的方法:

  • 当列表中还有一个元素
  • 查找最小起始元素
    • 将其添加到结果列表中,并从列表中删除
    • 当结果列表中存在一个Start大于最后一个item的End的元素时
      • 将其添加到结果列表中,并从列表中删除

类似:

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