Разработка структуры данных для объединения расписаний собраний.

Question

Меня попросили спроектировать структуру данных для расписаний собраний и затем объединить их. Например, если у человека А встреча с 9:00 до 10:00, а у человека Б встреча с 9:30 до 11:30, то объединенный интервал занятости - с 9:00 до 11:30.

Я создал классы для Персона, и в этом классе есть коллекция объектов собраний. Класс Meeting имеет время начала [чч: мм] в 24-часовом формате, так что я могу легко провести сравнение.

class Person {
String name;
Collection<Meeting> meetings;

}


class Meeting{
int hh, mm;
int duration; // duration will be in minutes from where we can get the end time. 
}

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

Любой лучший дизайн приветствуется.

Answer 1

Как @Anonymouse предложил, вы можете использовать 96 бит, то есть 12 байтов, для представления дня, поэтому 30-минутное собрание, начинающееся в 1:00, будет представлено как 110000, и вы можете использовать простые |работа со всеми числами.

Время O (n) Память O (12n) байт.Теоретически это было бы намного быстрее.

---

При условии собрания [время начала в минуту, время окончания в минуту].

Слияние двух собраний (Sa & Sb) в Sc при наложении

Sc [минимум (SA-начало, SB-начало), максимум (SA-конец, SB-конец)] и хранение объединенных собраний в коллекции.Если они не перекрываются, вы можете хранить их отдельно.

Мы знаем, что общее количество минут в дне = 24 * 60 = 1440 Если у вас есть 15-минутная единица, тогда она становится 24 * 60/15 = 96 (меньше 1 байта).)

Таким образом, вам нужно 2 байта на расписание, т. Е. Начало байта, конец.

Время O (n) Память O (2n) байта

---

Оба подхода выиграны 'не работает, если вам нужно удалить встречу позже.Для этого вам определенно стоит хранить все оригинальное расписание встреч отдельно.

Answer 2

Поскольку нереально планировать встречи с временными интервалами менее 15 минут, я бы согласился на ... a long. 64 бита в день, этого достаточно на 16 часов; Мне не нужно так много. Или, если хотите, используйте два длинных / три целых дня для полного дня.

Слияние - это операция |. Для больших временных интервалов я могу сдвинуть- или их, а затем проверить наличие неустановленных битов в качестве времени начала встречи. Эта сильно сжатая структура данных надломит любой индекс просто из-за операций низкого уровня. Кэш-память процессора может соответствовать расписанию сотен дней / пользователей.

Answer 3

Это классическая проблема Планирование задач .