c# - 如何获得一系列时间 block 的所有非重叠排列？

Question

我有一个似乎很简单的问题，我很难用代码 (C#) 建模 -

我正在尝试寻找参加 session 的人可以获得的最高潜在学分。类(class)有时间段，例如 Security 101 @ 9AM-10AM，Finance 202 @ 4PM-6PM 等。

主要规则是，您不能同时参加两门类(class) - 因此您将获得 9-10 和 10-11 类(class)的学分，但您不能同时获得 9-11 类(class)的学分.

我想做的是:

我想在一天内获取一组有效(有效意味着不重叠)路径。

因此，例如，一天的全套类(class)可能如下:

|---------------------------------------------------|
| 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     |
|---------------------------------------------------|

有人可能会在这一天走几条路:

• 财务 101 (9-10) -> 财务 102 (10-11) -> 安全 101 (11-12) -> 完成
• 金融 101 (9-10) -> PYTHON 300 (10-11) -> 安全 101 (11-12) -> 完成
• 财务 101 (9-10) -> 财务 102 (10-11) -> 数据库 200 (11-1) -> 完成
• 金融 101 (9-10) -> PYTHON 300 (10-11) -> 数据库 200 (11-1) -> 完成
• 经济学 101 (9-12)-> 完成

这是一个有点简单的场景，实际上可能有多个分支场景，例如三个朝九晚十的类(class)会在此基础上创建更多排列。

我想要一系列路径(而不是一个单一的最优路径)的原因是因为不一定有直接的 1 小时 = 1 学分相关性，会有基于路径集的二级计算对路径的学时值求和以确定什么是“最佳”。

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

为解决方案编辑:

感谢大家的投入和帮助，这两个解决方案都来自 Bradley Uffner和 Xiaoy312搞定了!

Answer 1

答案改编自Ordered Permutation of List<Int> :

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

输出:

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