Эффективный доступный таймер

Question

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

Назначение 1: 9-11-11 Назначение 2: 2 вечера до 5 вечера

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

8 am-9am 11 утра-2 вечера 5 pm-6pm

Итак, у меня есть класс 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...

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

Answer 1

Я думаю, что этот подход был бы асимптотически очень эффективным для огромных наборов данных (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. Прокрутка всех встреч, для всех дней и всех пользователей и добавление встреч (вместе с записью, для какого пользователя и дня) в соответствующий список для и времени начала и окончания встречи. Этот шаг - O (d * u * n), если вы используете связанный список и каждый раз добавляете их в начало списка.

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

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

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

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

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

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

Answer 2

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

Answer 3

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

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

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

Answer 4

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

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