Группировка объектов в период времени для создания минимальных групп

Question

У меня есть коллекция объектов, которые содержат свойство DateTime, DueDate.

Я хочу сгруппировать эти объекты так, чтобы

• свойства DueDate находились в пределахчас друг друга (не один и тот же час как таковой , но в течение 60 минут друг от друга
• наименьшее количество групп (каждый объект должен появляться только в одной группе).

В настоящее время у меня это есть, но оно группируется по часовому номеру , а не по 60 минутам:

var interval = new TimeSpan(1, 0, 0);  // 1 hour
var groupedByDueDateHour in from job in jobs
                                 group job by job.DueDate.Value.Ticks / interval.Ticks
                                 into g
                                 select g)

Как группировать по окно времени для того, чтобы произвести минимальное количество групп?

Answer 1

Подход с использованием грубой силы, возможно, существует более элегантное решение Linq, но это кажется правильным

public class Job
{ 
    public int ID { get; set; }
    public string Name { get; set; }
    public DateTime DueDate { get; set; }
}

// You need to have this list ordered by DueDate....
List<Job> myJobs = new List<Job>
{
    new Job{ID = 6, Name = "Job6", DueDate = new DateTime(2019,11,6,0,0,0)},
    new Job{ID = 7, Name = "Job7", DueDate = new DateTime(2019,11,6,0,0,0)},

    new Job{ID = 1, Name = "Job1", DueDate = new DateTime(2019,11,6,12,52,0)},
    new Job{ID = 2, Name = "Job2", DueDate = new DateTime(2019,11,6,13,51,0)},
    new Job{ID = 3, Name = "Job3", DueDate = new DateTime(2019,11,6,14,50,0)},
    new Job{ID = 4, Name = "Job4", DueDate = new DateTime(2019,11,6,15,49,0)},
};

Dictionary<int, List<Job>> grouped = new Dictionary<int, List<Job>>();

foreach (Job j in myJobs)
{
    int key = j.DueDate.Hour * 60 + j.DueDate.Minute;
    if(key == 0) key = -1; // for distinguish jobs due at midnight.
    int v = grouped.Keys.FirstOrDefault(k => (key - k) <= 60);
    if (v == 0)
        grouped.Add(key, new List<Job>(new Job[] { j}));
    else
        grouped[v].Add(j);
}

Это должно вернуть словарь, в котором каждый ключ - это минуты DueDate с полуночи, а каждое значение -список заданий, которые находятся в 60-минутном диапазоне от клавиши

для проверки с вашими реальными данными

Answer 2

Чтобы создать более удобное решение Linqy, вы можете начать с создания универсального метода группировки, который группирует последовательные элементы последовательности на основе определенных пользователем критериев. Ниже приведена простая реализация такого метода:

public static IEnumerable<List<TSource>> GroupConsecutive<TSource>(
    this IEnumerable<TSource> source,
    Func<TSource, IList<TSource>, bool> predicate)
{
    List<TSource> list = null;
    IList<TSource> readOnlyList = null;
    foreach (var item in source)
    {
        if (list == null || !predicate(item, readOnlyList))
        {
            if (list != null) yield return list;
            list = new List<TSource>();
            readOnlyList = new ReadOnlyCollection<TSource>(list);
        }
        list.Add(item);
    }
    if (list != null) yield return list;
}

predicate - это лямбда, которая принимает текущий элемент вместе с текущей группой и должна возвращать логическое значение, обозначающее, принадлежит ли элемент кгруппа или нет. true означает, что она принадлежит группе, а false означает, что она не принадлежит, поэтому текущая группа была завершена и должна быть создана новая, содержащая изначально только текущий элемент.

Затем вы можете использовать этот метод для решения вашей первоначальной проблемы, отсортировав объекты по DueDate, а затем сгруппировав их, сравнив DueDate каждого из них с DueDate первого элемента текущей группы. Если TimeSpan меньше или равно 60 минутам, то элемент принадлежит текущей группе. Этот алгоритм должен производить минимальное количество групп.

var source = new List<(int Id, DateTime DueDate)>();
source.Add((1, new DateTime(2020, 1, 1, 1, 30, 0)));
source.Add((2, new DateTime(2020, 1, 1, 1, 40, 0)));
source.Add((3, new DateTime(2020, 1, 1, 3, 20, 0)));
source.Add((4, new DateTime(2020, 1, 1, 4, 10, 0)));
source.Add((5, new DateTime(2020, 1, 1, 5, 10, 0)));

var groups = source
    .OrderBy(x => x.DueDate)
    .GroupConsecutive((item, group) =>
        (item.DueDate - group[0].DueDate).Duration().TotalMinutes <= 60);

foreach (var group in groups)
{
    Console.WriteLine($"Group: {String.Join(", ", group)}");
}

Вывод:

Группа: (1, 01.01.2020 01:30:00), (2,01.012020 01:40:00)
Группа: (3, 01.012020 03:20:00), (4, 01.012020 04:10:00)
Группа:(5.01.012020 05:10:00)