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

Question

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

我正在努力为参加会议的人寻找最高的潜在信用时间。课程有时间安排，例如保安101 @9时至上午10时、财务202 @4pm至下午6时等。

主要的规则是，你不能同时参加两门课程--所以你可以在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学分小时相关性，而是根据路径集进行二级计算，以确定路径的信用小时值，以确定什么是“最佳”。

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

为解决方案编辑：

感谢大家的投入和帮助，来自Bradley Uffner和Xiaoy312的解决方案都做到了！

​

​

Answer 1

这将递归地遍历课程列表，选择上一次课程结束后开始的任何课程。

它可能没有@晓y 312的答案那么有效，但它展示了另一种方法。我还添加了课程学分，显示特定路径的总学分，以及选择最佳路径。

通过添加一个适当的CourseLoad类来存储类列表，而不是使用List<>和List<List<>>，可以显着地清除这些问题。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading.Tasks;

namespace CoursePath
{
    class Program
    {
        static void Main(string[] args)
        {
            var courses = new List<CourseInfo>()
                          {
                              new CourseInfo("Finance 101", 1, DateTime.Parse("9:00 AM"), DateTime.Parse("10:00 AM")),
                              new CourseInfo("Finance 102", 2, DateTime.Parse("10:00 AM"), DateTime.Parse("11:00 AM")),
                              new CourseInfo("Python 300", 3, DateTime.Parse("10:00 AM"), DateTime.Parse("11:00 AM")),
                              new CourseInfo("Security 101", 4, DateTime.Parse("11:00 AM"), DateTime.Parse("12:00 PM")),
                              new CourseInfo("Economics 201", 5, DateTime.Parse("9:00 AM"), DateTime.Parse("12:00 PM")),
                              new CourseInfo("Database 200", 6, DateTime.Parse("11:00 AM"), DateTime.Parse("1:00 PM"))
                          };

            var results = new List<List<CourseInfo>>();

            BuildCourseList(null, courses, results);

            results.ForEach(c => Console.WriteLine(string.Join(" -> ", c.Select(x => x.Name)) + $" -> Done ({c.Sum(x => x.Credits)} credits)"));
            Console.WriteLine();
            var optimal = results.Select(path => new {Path = path, TotalCredits = path.Sum(c => c.Credits)}).OrderByDescending(path => path.TotalCredits).First();
            Console.WriteLine("Optimal Path: " + string.Join(" -> ", optimal.Path.Select(x => x.Name)) + $" -> Done ({optimal.TotalCredits} credits)");
            Console.Read();
        }

        public static void BuildCourseList(List<CourseInfo> currentPath, List<CourseInfo> courses, List<List<CourseInfo>> results)
        {
            CourseInfo currentCourse = currentPath?.LastOrDefault();
            var candidates = (currentCourse == null ? courses : courses.Where(c => c.StarTime >= currentCourse.EndTime));
            if (currentPath != null)
            {
                results.Add(currentPath);
            }
            foreach (var course in candidates)
            {
                var nextPath = currentPath == null ? new List<CourseInfo>() : new List<CourseInfo>(currentPath);
                nextPath.Add(course);
                BuildCourseList(nextPath, courses, results);
            }
        }
    }

    public class CourseInfo
    {
        public CourseInfo(string name, int credits, DateTime starTime, DateTime endTime)
        {
            Name = name;
            Credits = credits;
            StarTime = starTime;
            EndTime = endTime;
        }

        public string Name { get; set; }
        public int Credits { get; set; }
        public DateTime StarTime { get; set; }
        public DateTime EndTime { get; set; }
    }
}

输出：

Finance 101 -> Done (1 credits)
Finance 101 -> Finance 102 -> Done (3 credits)
Finance 101 -> Finance 102 -> Security 101 -> Done (7 credits)
Finance 101 -> Finance 102 -> Database 200 -> Done (9 credits)
Finance 101 -> Python 300 -> Done (4 credits)
Finance 101 -> Python 300 -> Security 101 -> Done (8 credits)
Finance 101 -> Python 300 -> Database 200 -> Done (10 credits)
Finance 101 -> Security 101 -> Done (5 credits)
Finance 101 -> Database 200 -> Done (7 credits)
Finance 102 -> Done (2 credits)
Finance 102 -> Security 101 -> Done (6 credits)
Finance 102 -> Database 200 -> Done (8 credits)
Python 300 -> Done (3 credits)
Python 300 -> Security 101 -> Done (7 credits)
Python 300 -> Database 200 -> Done (9 credits)
Security 101 -> Done (4 credits)
Economics 201 -> Done (5 credits)
Database 200 -> Done (6 credits)

Optimal Path: Finance 101 -> Python 300 -> Database 200 -> Done (10 credits)

Answer 2

从Ordered Permutation of List改编的答案

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