如何获得一系列时间块的所有非重叠排列？

我有一个似乎很简单的问题，我很难在代码（C#）中建模 -

我正在努力寻找参加会议的人可获得的最高潜在学分。课程有时间段，例如安全 101 @ 9AM-10AM，金融 202 @ 4PM-6PM 等。

主要规则是，您不能同时参加两门课程 - 因此您将获得 9-10 和 10-11 课程的学分，但您不能同时获得 9-11 课程的学分。

我想做的是：

我想获得一天中有效（有效意味着不重叠）路径的数组。

例如，一天的全套课程可能如下：

|---------------------------------------------------|
| COURSE            |   START       |   END         |
|-------------------|---------------|---------------|
| FINANCE 101       |   9:00 AM     |   10:00 AM    |
| FINANCE 102       |   10:00 AM    |   11:00 AM    |
| PYTHON 300        |   10:00 AM    |   11:00 AM    |
| SECURITY 101      |   11:00 AM    |   12:00 PM    |
| ECONOMICS 101     |   9:00 AM     |   12:00 PM    |
| DATABASE 200      |   11:00 AM    |   1:00 PM     |
|---------------------------------------------------|

人们这一天可能会走以下几条路：

• FINANCE 101 (9-10) -> FINANCE 102 (10-11) -> SECURITY 101 (11-12) -> DONE
• FINANCE 101 (9-10) -> PYTHON 300 (10-11) -> SECURITY 101 (11-12) -> DONE
• FINANCE 101 (9-10) -> FINANCE 102 (10-11) -> DATABASE 200 (11-1) -> DONE
• FINANCE 101 (9-10) -> PYTHON 300 (10-11) -> DATABASE 200 (11-1) -> DONE
• ECONOMICS 101 (9-12)-> DONE

这是一个有点简单的场景，实际上可能有多个分支场景，例如拥有三门 9-10 课程，这将在此基础上创建更多排列。

我想要一组路径（而不是一个最佳路径）的原因是因为不一定有直接的 1 小时 = 1 学时相关性，将有基于路径集的第二级计算来求和路径的学分值决定什么是“最佳”。

我的问题是 - 是否有一种技术或软件模式可供我遵循来生成这些排列，以便我可以衡量结果以确定为课程学习者带来最多学分的路径？

编辑解决方案：

感谢大家的意见和帮助，这两个解决方案都来自布拉德利乌夫纳 https://stackoverflow.com/users/526724/bradley-uffner and Xiaoy312 https://stackoverflow.com/users/561113/xiaoy312搞定了！

答案改编自列表的有序排列 https://stackoverflow.com/questions/42840771/ordered-permutation-of-listint:

public static class CourseExtensions
{    
    public static IEnumerable<IEnumerable<Course>> GetPermutations(this IEnumerable<Course> courses)
    {
        return GetCoursesHelper(courses, TimeSpan.Zero);
    }
    private static IEnumerable<IEnumerable<Course>> GetCoursesHelper(IEnumerable<Course> courses, TimeSpan from)
    {        
        foreach (var course in courses)
        {
            if (course.Start < from) continue;

            yield return new[] { course };

            var permutations = GetCoursesHelper(courses, course.End);
            foreach (var subPermutation in permutations)
            {
                yield return new[]{ course }.Concat(subPermutation);
            }
        }
    }
}

完整代码：

void Main()
{
    foreach (var courses in GetCourses().GetPermutations())
    {
        Console.WriteLine(string.Join(" -> ", courses
            .Select(x => x.ToString())
            .Concat(new [] { "DONE" })));
    }
}

// Define other methods and classes here
public class Course
{
    public string Name { get; set; }
    public TimeSpan Start { get; set; }
    public TimeSpan End { get; set; }

    public override string ToString()
    {
        return string.Format("{0} ({1:hhmm}-{2:hhmm})",
           Name, Start, End);
    }
}

IEnumerable<Course> GetCourses() 
{
    var data = @"
| FINANCE 101       |   9:00 AM     |   10:00 AM    |
| FINANCE 102       |   10:00 AM    |   11:00 AM    |
| PYTHON 300        |   10:00 AM    |   11:00 AM    |
| SECURITY 101      |   11:00 AM    |   12:00 PM    |
| ECONOMICS 101     |   9:00 AM     |   12:00 PM    |
| DATABASE 200      |   11:00 AM    |   1:00 PM     |
".Trim();

    return data.Split('\n')
        .Select(r => r.Split('|').Select(c => c.Trim()).ToArray())
        .Select(x => new Course
        {
            Name = x[1],
            Start = DateTime.ParseExact(x[2], "h:mm tt", CultureInfo.InvariantCulture).TimeOfDay,
            End = DateTime.ParseExact(x[3], "h:mm tt", CultureInfo.InvariantCulture).TimeOfDay
        });
}

public static class CourseExtensions
{    
    public static IEnumerable<IEnumerable<Course>> GetPermutations(this IEnumerable<Course> courses)
    {
        return GetCoursesHelper(courses, TimeSpan.Zero);
    }
    private static IEnumerable<IEnumerable<Course>> GetCoursesHelper(IEnumerable<Course> courses, TimeSpan from)
    {        
        foreach (var course in courses)
        {
            if (course.Start < from) continue;

            yield return new[] { course };

            var permutations = GetCoursesHelper(courses, course.End);
            foreach (var subPermutation in permutations)
            {
                yield return new[]{ course }.Concat(subPermutation);
            }
        }
    }
}

Output:

FINANCE 101 (0900-1000) -> DONE
FINANCE 101 (0900-1000) -> FINANCE 102 (1000-1100) -> DONE
FINANCE 101 (0900-1000) -> FINANCE 102 (1000-1100) -> SECURITY 101 (1100-1200) -> DONE
FINANCE 101 (0900-1000) -> FINANCE 102 (1000-1100) -> DATABASE 200 (1100-1300) -> DONE
FINANCE 101 (0900-1000) -> PYTHON 300 (1000-1100) -> DONE
FINANCE 101 (0900-1000) -> PYTHON 300 (1000-1100) -> SECURITY 101 (1100-1200) -> DONE
FINANCE 101 (0900-1000) -> PYTHON 300 (1000-1100) -> DATABASE 200 (1100-1300) -> DONE
FINANCE 101 (0900-1000) -> SECURITY 101 (1100-1200) -> DONE
FINANCE 101 (0900-1000) -> DATABASE 200 (1100-1300) -> DONE
FINANCE 102 (1000-1100) -> DONE
FINANCE 102 (1000-1100) -> SECURITY 101 (1100-1200) -> DONE
FINANCE 102 (1000-1100) -> DATABASE 200 (1100-1300) -> DONE
PYTHON 300 (1000-1100) -> DONE
PYTHON 300 (1000-1100) -> SECURITY 101 (1100-1200) -> DONE
PYTHON 300 (1000-1100) -> DATABASE 200 (1100-1300) -> DONE
SECURITY 101 (1100-1200) -> DONE
ECONOMICS 101 (0900-1200) -> DONE
DATABASE 200 (1100-1300) -> DONE