У Контура более 10 тыс сотрудников и очень-очень много групповых встреч: около 30 тыс ежемесячно, мы считали. ? И бывает так, что нужно собрать сразу нескольких ребят в наиболее удобное для всех время. И начинается вот это вот: зайти на страницу человечка > посмотреть, какое время у него свободно > сопоставить со своим > проверить, а могут ли в это время остальные участники > обнаружить, что нет, и идти заново по кругу смотреть другие слоты, забывая, чё там у кого. ? Да блин!
Мы решили остановить эту котовасию✋?и добавить в наш внутренний портал (в Контуре используется Стафф) рекомендацию свободных слотов для всех участников встречи. Рассказываем и показываем, как реализовали это.
Но для начала, что такое Стафф.
Это внутренний веб-портал для сотрудников Контура: комбинация новостной платформы и справочника. Здесь можно найти информацию о коллегах, формировать сообщества, получать новости от разных отделов, выпускать статьи и общаться в комментариях.
Стафф используется во многих рабочих процессах, и, чтобы не «выбиваться из контекста», не выходя из инструмента удобно просматривать занятость коллег в календаре и планировать встречи. Чтобы быстро планировать созвоны с большим количество участников мы решили добавить в этот календарь рекомендацию слотов.
Вот так это выглядит: когда ты выбрал всех участников, планировщик предлагает слоты, которые свободны одновременно у всех этих людей. И ничего не надо идти проверять самостоятельно. ?
Наша система:
Встроена в процесс планирования встреч.
Проверяет календари участников встречи и свободные переговорки.
Сама предлагает слоты когда это нужно, анализируя ситуацию.
Даёт возможность выбирать слоты в один клик и высвобождает время на другие дела.
Самое популярное время — 60 минут, его мы и выбрали как максимальное для нашего рекомендательного слота.
Можно сразу внести время встречи, например, с 17:00 до 17:15, выбрать участников. А система предложит все свободные слоты и переговорки, куда можно пойти.
Что ещё умеет наша система:
Работает для любого количества участников: от двух до бесконечности.
Предлагает слоты только с одной переговоркой, не требующей согласования. Адрес переговорки определяется в контексте текущих настроек места, а приоритет в предложениях — ближайшая к вашему этажу или первая по порядку, если адрес не по месту работы.
Предлагаемые слоты — это общее ближайшее свободное время для всех участников и переговорки с 10:00 по 18:00 по часовому поясу организатора. Поддерживаем только этот период как самый сложный в планировании.
Слоты одного дня предлагает по одному до 14:00 и после, чтобы закрыть предпочтения по разным периодам проведения встречи в течение дня.
Рабочие дни определяются в соответствии с производственным календарем, чтобы минимизировать ошибки в планировании.
Дальность поиска слотов — 2 недели.
Рекомендации работают только для разовых встреч, регулярные пока не поддерживаются.
Система предлагает до четырёх ближайших слотов с переговоркой и/или без, а те, кому не подходят предложенные варианты, могут воспользоваться опцией «Поиск слотов», где можно выбрать слоты любой продолжительности и перебрать найденные варианты переговорок.
А что же внутри??
Есть два вида запросов: за календарём офиса, который учитывает занятость переговорок на 1 день, и за рекомендациями слотов, которые учитывают занятость на две недели вперёд.
Запрос за рекомендациями выглядит так: https://api/calendar/suggest.
Вот немного метрик по обоим запросам: видно, что медианный запрос всего в два раза дольше.
Поиск слотов для участников
Здесь всё кажется простым: есть список email-ов участников, стартовая дата, и конечная дата для поиска. По этим параметрам первым запросом к базе данных Стаффа, используя новый бэкенд календарей, получаем все встречи в указанном промежутке.
// Получаем события календарей участников
var calendarItems = await calendarService.GetEvents(emails, searchStartDate, searchEndDate);
// Ищем свободные слоты
var freeIntervals = FindFreeIntervals(calendarItems.Values, searchStartDate, searchEndDate, chillTime);И ищем свободные интервалы — записываем в currentFreeInterval первый подходящий слот, сортируем все встречи по времени начала и идём по его возрастанию. Если очередная встреча пересекается с currentFreeInterval, то объединяем их и записываем в currentFreeInterval, иначе им становится новый промежуток, а разницу между временем начала и конца добавляем к результату.
var busyIntervals = calendarItems
.SelectMany(s => s.Where(item => item.BusyType != BusyType.Free))
.Select(s => new TimeInterval(s.StartDate, s.EndDate))
.Concat(chillTime?? [])
.ToList();
// Сортируем занятые интервалы по времени начала
busyIntervals.Sort((a, b) => a.StartDate.CompareTo(b.StartDate));
var firstInterval = busyIntervals.Count > 0 ? new TimeInterval?(busyIntervals.First()) : null;
// Инициализируем текущий свободный интервал
var currentFreeInterval = new TimeInterval(minDate, firstInterval?.StartDate ?? maxDate);
yield return currentFreeInterval;
// Если первого интервала нет, значит busyIntervals пустой и там только один слот
if (firstInterval is null)
yield break;
// Перебираем занятые интервалы
for (var i = 0; i < busyIntervals.Count - 1; i++)
{
var currentInterval = busyIntervals[i];
var nextInterval = busyIntervals[i + 1];
if (currentInterval.Overlaps(nextInterval))
{
busyIntervals[i + 1] = currentInterval.Combine(nextInterval);
continue;
}
currentFreeInterval = new TimeInterval(currentInterval.EndDate, nextInterval.StartDate);
yield return currentFreeInterval;
}
// Добавляем последний свободный интервал
currentFreeInterval = new TimeInterval(busyIntervals[^1].EndDate, maxDate);
yield return currentFreeInterval;
Таким образом для θ(n) встреч всех участников получаем θ(n * log(n)) времени и θ(n) памяти, что почти не отличимо от линейной обработки по типу обычного маппинга.
А дальше делим полученные промежутки на интервалы заданной длины и возвращаем фронтенду.
Небольшая хитрость с рабочим временем
Напомню, что слоты должны искаться с 10:00 до 18:00 в часовом поясе автора запроса. Было бы неэффективно сначала искать кучу свободных слотов лишние 16 часов в каждых сутках, особенно если учитывать, что встреч там почти ни у кого нет, а потом фильтровать их. Поэтому ко встречам, полученным из запроса к базе, мы добавляем фейковую занятость на нерабочее время.
var chillTime = filter.CreateFakeMeetings(holidaysDates);
var intervals = await FindAsync(filter.Emails, filter.StartDate, filter.EndDate, filter.Duration, chillTime);А вот так она создаётся:
var workDays = filter.WorkingDaysSource.HasFlag(WorkingDaysSourceType.WorkDaysOfWeek)
? filter.DaysOfWeek
: _allWeek;
var startDate = filter.StartDate.Date;
var endDate = filter.EndDate.Date;
var result = new List<TimeInterval>
{
new(startDate.AddDays(-2), filter.StartDate),
new(filter.EndDate, endDate.AddDays(3))
};
if (filter.TimeZoneSpan == TimeSpan.Zero)
for (var currentDate = startDate;
currentDate <= endDate;
currentDate = currentDate.AddDays(1))
{
if (holidaysDates.Contains(currentDate.Date) || !workDays.Contains(currentDate.DayOfWeek))
result.Add(new TimeInterval(currentDate, currentDate.AddDays(1)));
else
{
result.Add(new TimeInterval(currentDate, currentDate.AddHours(filter.WorkStartHour)));
result.Add(new TimeInterval(currentDate.AddHours(filter.WorkEndHour), currentDate.AddDays(1)));
}
}
Кстати, рекомендация слотов учитывает производственный календарь, и поэтому может рекомендовать встречи на рабочие субботы (например, 1 ноября), но при этом не предлагать их на новогодние каникулы.
Пересечение слотов со свободным временем переговорок
Реализовано тоже не очень сложно, но чуть хитрее. Подходящие интервалы для списка обязательных участников возьмём из прошлой части.
Также первым запросом получаем все встречи в выбранном промежутке у переговорок в офисе, которые можно бронировать всем. А дальше надо пересечь их отдельно для каждой переговорки со слотами для участников.
public async Task<Dictionary<string, TimeInterval[]>> FilterSlotsForRoomsAsync(List<TimeInterval> freeIntervals,
IEnumerable<string> roomsEmails, DateTime startDate, DateTime endDate)
{
var calendarsItems = await calendarService.GetEvents(roomsEmails, startDate, endDate);
return calendarsItems.Select(item =>
(roomEmail: item.Key, Intervals: FilterIntervalsByMeetings(freeIntervals, item.Value)))
.Where(val => val.Intervals.Length > 0)
.ToDictionary(item => item.roomEmail, item => item.Intervals);
}В этом нам поможет алгоритм двух указателей. Свободные слоты уже отсортированы, объединяем соседние встречи переговорки и сортируем их. А затем проходимся по слотам и параллельно по коллекции встреч, и добавляем в результат только слоты, которые подходят и для переговорки.
private static TimeInterval[] FilterIntervalsByMeetings(List<TimeInterval> timeIntervals, CalendarItem[] calendarItems)
{
var result = new List<TimeInterval>();
// Объединяет пересекающиеся интервалы (если они есть) и сортирует по возрастанию времени начала
using var roomMeetings = CombineIntervals(calendarItems
.Select(item => new TimeInterval(item.StartDate, item.EndDate))
.OrderBy(item => item.StartDate))
.GetEnumerator();
roomMeetings.MoveNext();
// Аналог 2-х указателей, только чуть красивее с Enumerator-ом вместо индексов
foreach (var timeInterval in timeIntervals)
{
// Устанавливает в roomMeetings.Current максимально близкий (не заканчивающийся раньше) интервал к timeInterval
// Если перенести MoveNext внутрь будет бесконечный цикл
while (roomMeetings.Current is not null
&& roomMeetings.Current.Value.EndDate <= timeInterval.StartDate
&& roomMeetings.MoveNext())
;
if (roomMeetings.Current is null || !timeInterval.StrongOverlaps(roomMeetings.Current.Value))
result.Add(timeInterval);
}
return result.ToArray();
}Для n свободных ранее найденных слотов у обязательных участников, m переговорок и k встреч в среднем у каждой их них получается θ (m (k log(k) + n)) по времени и θ (m * k + n) по памяти.
Значительно лучше очевидного решения с асимптотикой
θ (m (n k))по времени. Имею в виду перебор для каждой переговорки всех слотов и проверку каждого на пересечение с её встречами.
Если говорить о точных числах, то для двухнедельного интервала k ~= 100, m~=30, n~=160 (при запросе на 2 недели по офису с интервалом в 30 минут). Разница времени обработки ответов от БД нашего решения и примитивного - в 16000 / 820 ~= 19 раз, и, соответственно, такая же разница в затрачиваемых ресурсах CPU.
А потом результаты по переговоркам сортируются (если искать их в своем офисе) по удалённости от своего этажа, так что важно указывать своё местоположение в офисе.
if (userFloor == null)
return roomsIntervals;
return rooms.Where(room => roomsIntervals.ContainsKey(room.Email))
.OrderBy(room => Math.Abs(userFloor.Value - room.GetFloorNumber()))
.ToDictionary(room => room.Email, room => roomsIntervals[room.Email]);Готовы ответить на вопросы, поэтому задавайте их в комментариях!