Сложность: medium
Вы создаете программу для использования в качестве календаря. Мы можем добавить новое событие, если его добавление не приведет к тройному бронированию. Тройное бронирование происходит, когда три события имеют некоторое непустое пересечение (т.е, Событие можно представить в виде пары целых чисел start и end, которая представляет собой бронирование на полуоткрытом интервале [start, end), диапазоне вещественных чисел x таких, что start <= x < end. Реализация класса MyCalendarTwo: MyCalendarTwo() Инициализирует объект календаря. boolean book(int start, int end) Возвращает true, если событие может быть успешно добавлено в календарь, не вызывая тройного бронирования. В противном случае возвращается false и событие не добавляется в календарь.
Пример:
Input
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, true, true, true, false, true, true]
👨💻 Алгоритм:
1⃣Создайте два списка: один для отслеживания всех событий, второй для отслеживания пересечений. подпоследовательностей.
2⃣При добавлении нового события сначала проверьте, не пересекается ли оно с любыми существующими пересечениями.
3⃣Если пересечение не обнаружено, добавьте новое событие и обновите список пересечений при необходимости.
😎 Решение:
class MyCalendarTwo {
constructor() {
this.events = [];
this.overlaps = [];
}
book(start, end) {
for (let [os, oe] of this.overlaps) {
if (start < oe && end > os) {
return false;
}
}
for (let [es, ee] of this.events) {
if (start < ee && end > es) {
this.overlaps.push([Math.max(start, es), Math.min(end, ee)]);
}
}
this.events.push([start, end]);
return true;
}
}Ставь 👍 и забирай 📚 Базу знаний