Блог

У меня есть набор встреч на определенный рабочий день, который длится с 8 утра до 18 вечера:

Прием с 1: 9 до 11:00 Прием с 2: 14 до 17:00

Я ищу эффективный способ найти свободное время. Таким образом, в этом случае доступное время будет:

с 8 утра до 9 утра, с 11 утра до 14:00, с 5 до 18:00

Итак, у меня есть класс TimeBlock

 class TimeBlock {
  public DateTime start
  public DateTime end
}

var appointments = new List<TimeBlock>();
var freeTimeBlocks = new List<TimeBlock>();

' add appointments
appointments.Add(new TimeBlock{start...
appointments.Add(new TimeBlock{start...
  

Я ищу эффективный способ найти свободное время, потому что алгоритм будет выполняться на довольно большом наборе данных.

Попробуйте это, предполагается, что нет совпадающих встреч:

 var orderedAppointments = appointments.OrderBy(a => a.start).ToArray();

freeTimeBlocks.Clear();

for(int i = 0; i < orderedAppointments.Length - 1; i  )
{
    freeTimeBlocks.Add(new TimeBlock(){ start = orderedAppointments[i].end; end = orderedAppointments[i   1].start });
}
var firstAppointment = orderedAppointments.First();
var lastAppointment = orderedAppointments.Last();

if(firstAppointment.start.Hour > 8)
   freeTimeBlocks.Add(new TimeBlock() { start = firstAppointment.Today.AddHours(8); end = firstAppointment.start });
if(lastAppointment.end.Hour < 18)
   freeTimeBlocks.Add(new TimeBlock() { start = lastAppointment.end; end = lastAppointment.Today.AddHours(18) });
  

Убедитесь, что временные блоки отсортированы ( O(nlogn) или лучше), затем выполните цикл по ним и создайте диапазоны доступности от конца каждого блока до начала следующего ( O(n) ).

Я думаю, что этот подход был бы асимптотически очень эффективным для огромных наборов данных (d * u >> n), если они могут поместиться в памяти:

Если количество дней равно d, количество пользователей равно u, а среднее количество встреч на пользователя в день равно n, это равно O (d * u * n), тогда как основанный на сортировке подход к каждому дню был бы больше похож на O (d * u * n * log n).

(Если u= 1 или d= 1, это не имеет значения — это не имеет значения.)

1. Создайте массив списков, проиндексированных по всем возможным временным интервалам. Например, если вы можете использовать временные интервалы каждые 5 минут, у вас будет массив размером 120. Этот шаг равен O (1). Мы предполагаем, что количество возможных временных интервалов фиксировано, и поэтому оно не должно иметь никакого отношения к анализу сложности.

2. Просмотрите все встречи для всех дней и всех пользователей и добавьте встречи (вместе с записью о том, для какого пользователя и в какой день это назначено) в соответствующий список для как времени начала, так и времени окончания встречи. Этот шаг выполняется автоматически, если вы используете связанный список и каждый раз добавляете их в начало списка.

3. Создайте массив для записи «текущего» свободного временного интервала для каждого дня и пользователя — вы увидите, как это работает на следующем шаге.

4. Выполните цикл по первому массиву, и для каждого списка в массиве выполните цикл по этому списку (таким образом, циклы являются вложенными). Для каждой встречи, которую вы видите с надписью «завершить встречу сейчас», начните записывать новый свободный временной интервал в это время, для этого дня и пользователя. Для каждой встречи, которую вы видите с надписью «начать встречу сейчас», завершите запись свободного временного интервала для этого дня и пользователя, если таковой имеется, и отбросьте его, если он равен нулевой продолжительности — если его нет и сейчас не 8 утра, создайте его. Этот шаг также является O (d * u * n).

5. Завершите все открытые записи о свободном времени в 18:00. Этот шаг является наихудшим вариантом O (d * u).

Не требуется сопоставлений или поиска между назначениями!

Это основано на сортировке по радиусу.

Однако я не уверен, будет ли это лучше на практике. Это, безусловно, требует больше места!

Могло бы быть так же просто, как это, при условии, что у вас нет никаких перекрывающихся встреч (из вашего заявления о проблеме, которое не должно быть возможным):

 appointments.Sort((a,b) => a.Start.CompareTo(b.Start));
for(int i = 0; i< appointments.Count-1; i  )
{
    if(appointments[i].End < appointments[i 1].Start)
        freeTimeBlocks.Add(new TimeBlock() { Start  = appointments[i].End, End = appointments[i 1].Start });
}
  

Это не учитывает крайние случаи нехватки времени до первой встречи и после последней, которые вам пришлось бы вручную проверять и добавлять.

Этот ответ также работает с предположением, что не будет никаких перекрывающихся встреч. Вместо того, чтобы работать с временными рамками с 8 утра до 6 вечера, указанными в вопросе, это решение позволяет установить один или несколько доступных периодов времени.

Я думаю, это можно сделать более элегантно, но я не могу понять, как это сделать.

 private static List<TimeBlock> GetDayOpenSlots(IEnumerable<TimeBlock> daySlots,
    IReadOnlyCollection<TimeBlock> usedDaySlots)
{
    var freeTimeBlocks = new List<TimeBlock>();
    foreach (var daySlot in daySlots)
    {
        var selectedSlotsWithinRange = usedDaySlots
            .Where(x => x.StartTime >= daySlot.StartTime amp;amp; x.EndTime <= daySlot.EndTime)
            .OrderBy(x => x.StartTime)
            .ToList();

        if (!selectedSlotsWithinRange.Any())
        {
            freeTimeBlocks.Add(daySlot);
            continue;
        }

        for (var i = 0; i < selectedSlotsWithinRange.Count - 1; i  )
        {
            var currentSlot = selectedSlotsWithinRange[i];
            var nextSlot = selectedSlotsWithinRange[i   1];
            if (currentSlot.EndTime == nextSlot.StartTime)
            {
                continue;
            }

            freeTimeBlocks.Add(new TimeBlock(currentSlot.EndTime,
                nextSlot.StartTime));
        }

        var firstAppointment = selectedSlotsWithinRange.First();
        var lastAppointment = selectedSlotsWithinRange.Last();

        if (firstAppointment.StartTime > daySlot.StartTime)
        {
            freeTimeBlocks.Add(new TimeBlock(daySlot.StartTime,
                firstAppointment.StartTime));
        }

        if (lastAppointment.EndTime < daySlot.EndTime)
        {
            freeTimeBlocks.Add(new TimeBlock(lastAppointment.EndTime, daySlot.EndTime));
        }
    }

    return freeTimeBlocks
        .OrderBy(x => x.StartTime)
        .ToList();
}