All geek questions in one place

How to get all non-overlapping permutations for a number of time blocks?

I have what seems like a simple problem that makes it difficult for me to model the code (C #) -

I am trying to find the highest potential credit hours for the person attending the conference. Courses have time blocks, such as Security 101 @ 9 AM-10AM, Finance 202 @ 4 PM-6PM, etc.

The main rule: you cannot attend two courses at the same time - so you will get a loan for courses from 9-10 and 10-11, but you also can not get credit for a course that lasted 9-11.

I would like to do the following:

I would like to get an array of valid (valid non-overlapping) paths throughout the day.

So, for example, a full set of courses during the day can be as follows:

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

There are several ways that someone can take during this day:

  • 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 Credit Hour, , , , "".

: , , , , , ?

:

, Bradley Uffner Xiaoy312

enter image description here

+4
3

, , .

, , @Xiaoy312 , . , , .

, 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)
+2

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

- ( ), , . : https://en.wikipedia.org/wiki/Independent_set_(graph_theory)

, :

: - , - .

() , :

The problem with independent maximum weight : the input is an undirected graph with weights at its vertices, and the output is an independent set with the maximum total weight

0
source

Source: https://habr.com/ru/post/1684913/

More articles:


All Articles