Решение: мой календарь I

LeetCode Solutions (161 серия деталей)

Это является частью серии объяснений решения LeetCode ( index ). Если вам понравилось это решение или нашли его полезным, Пожалуйста, нравится Этот пост и/или upvote Мое решение по сообщению на форумах LeetCode Анкет

Проблема LeetCode #729 (среда): мой календарь I

Описание:

( прыгнуть в : Идея решения Код : JavaScript | Python | Java | C ++

Реализовать Mycalendar класс для хранения ваших мероприятий. Новое событие может быть добавлено, если добавление события не приведет к двойному бронированию.

Ваш класс будет иметь метод, Книга (int start, int end) Анкет Формально это представляет собой бронирование на половине открытого интервала [начать конец) , диапазон реальных чисел x тако, что Начал <конец Анкет

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

Для каждого вызова метода Mycalendar.book , вернуть истинный Если событие может быть успешно добавлен в календарь, не вызывая двойного бронирования. В противном случае, возвращайте ложный и не добавляйте событие в календарь.

Ваш класс будет называться таким: MycAlendar MyCalendar () ; Mycalendar.book (Start, End)

Примеры:

Ограничения:

• Количество вызовов Mycalendar.book за тестовый пример будет не более чем 1000 Анкет
• В призывах к Mycalendar.book (Start, End) , старт и конец целые числа в диапазоне [0, 10^9] .

Идея:

( Прыгните к : Описание задачи Код : JavaScript | Python | Java | C ++

Поскольку бронирование не разрешается перекрываться, нам, естественно, нужно отсортировать данные каким -то образом, чтобы мы могли найти правильную позицию вставки каждого нового бронирования и проверить обоснованность бронирования.

Наивное решение здесь заключается в том, чтобы использовать массив и каждый раз прибегать его в Сложность времени из O (n * log n) Анкет С другой стороны, мы могли бы использовать Бинарный поиск Чтобы найти правильную позицию, затем вставьте бронирование на эту позицию, но это потребует O (log n) время Для бинарного поиска и другого O (n) время для вставки.

( Важное примечание : Очевидно, каждый из четырех языков За исключением javascript имеет сортированную структуру данных, основанную на структуре красно-черное ) время , а не Вовремя Это потребуется для стандартной вставки массива. Это в сочетании с O (log n) время Для бинарного поиска этот подход делает этот подход быстрее, чем связанный список. См. Обновленный раздел ниже для объяснения.)

Python, Java, & C ++: Python, Java и C ++ разрешают отсортированную структуру данных только с O (log n) вставка. В этом подходе мы сначала используем Бинарный поиск Функция, чтобы найти правильную позицию вставки, затем сравните старт и конец нового бронирования в существующее Календарь Записи, чтобы проверить обоснованность нового бронирования.

Чтобы не сравнивать более одного Календа Вход для проверки (как поиск другой записи может занять еще одну O (log n) время ), мы можем хранить записи в обратном порядке в Календарь ( {end, start} ), затем найдите верхняя граница бронирования с использованием правильного порядка ( {Start, End} ).

Давайте рассмотрим разрыв в бронировании, который выглядит так:

  |---------|               |---------|

Если мы сравниваем Начало против старт в нашем Бинарный поиск , мы могли бы получить следующие сценарии:

  S---------|               S---------|
   <----------------------->                 // binary search range
       S---------|                           // possibility #1
               S---------|                   // possibility #2
                       S---------|           // possibility #3

Это означает, что нам придется получить доступ оба Окружающие заказы, чтобы проверить, очищает ли новое бронирование оба предыдущего бронирования конец и следующее бронирование старт Анкет Если вместо этого мы храним заказы с старт и конец Перевернутый, двоичный поиск автоматически очистит предыдущее бронирование конец , что означает, что эти три сценария переходят к этому:

  |---------E               |---------E
             <----------------------->       // binary search range
               S---------|                   // possibility #1
                       S---------|           // possibility #2
                                 S---------| // possibility #3

Это означает, что нам нужно только получить доступ к бронированию, возвращаемому бинарным поиском, сохранив нам O (log n) время Для второго поиска, а также только требует единственной условной проверки ( new.end.start ), а не два.

Если бронирование недействительно, мы можем вернуть false , в противном случае мы можем вставить новое бронирование в Календарь (в обратном порядке), а затем вернуть истинность Анкет Мы также можем вставить бронирование хвоста на Календарь Инициализация, чтобы облегчить сравнение.

JavaScript: Для JavaScript мы можем использовать Связанный список Подход, поскольку поиск в связанном списке будет только Вовремя и вставка будет только O (1) время . Мы должны начать с определения нашего пустого списка бронирования ( Head ) с помощью головного узла и хвостового узла в качестве книг для данных бронирования.

Для Книга Функция, мы будем повторять через связанный список, пока не найдем бронирование, которое начнется после нашего попытки бронирования ( curr ). Мы также должны помнить, чтобы отслеживать Последний Узел также, чтобы мы могли зашить новое бронирование в список.

Как только мы нашли правильный узел, мы должны проверить, будет ли новое бронирование перекрываться, и вернуть false Если это так. В противном случае мы должны создать наш новый узел и вставить его между Последний и Curr , тогда вернуть истинность Анкет

• Сложность времени:
  • Одиночное бронирование с сортированным деревом: O (log n) куда N Длина календаря
  • Одиночное бронирование с списком связан: НА)
  • Полная серия с сортированным деревом: O (n * log n)
  • Полная серия со списком связан: O (n^2)
• Сложность пространства: O (n) для календаря

Код JavaScript:

( Прыгните к : Описание задачи Идея решения )

class MyCalendar {
    constructor() {
        this.calendar = {start: -1, end: -1, next: {start: Infinity, end: Infinity}}
    }
    book = function(start, end) {
        let curr = this.calendar, last = curr
        while (start >= curr.end)
            last = curr, curr = curr.next
        if (curr.start < end)
            return false
        last.next = {start: start, end: end, next: curr}
        return true
    };
}

Код Python:

( Прыгните к : Описание задачи Идея решения )

from sortedcontainers import SortedDict
class MyCalendar:
    def __init__(self):
        self.calendar = SortedDict({float('inf'):float('inf')})        
    def book(self, start: int, end: int) -> bool:
        ix = self.calendar.bisect_right(start)
        k,v = self.calendar.peekitem(ix)
        res = end <= v
        if res: self.calendar[end] = start
        return res

W/связанный список:

class MyCalendar:
    def __init__(self):
        self.calendar = {'start': -1, 'end': -1, 'next': {'start': float('inf'), 'end': float('inf')}}
    def book(self, start: int, end: int) -> bool:
        curr = self.calendar
        while start >= curr['end']:
            last, curr = curr, curr['next']
        if curr['start'] < end:
            return False
        last['next'] = {'start': start, 'end': end, 'next': curr}
        return True

Код Java:

( Прыгните к : Описание задачи Идея решения )

class MyCalendar {
    TreeMap calendar = new TreeMap<>();
    public MyCalendar() {
        calendar.put(Integer.MAX_VALUE, Integer.MAX_VALUE);
    }
    public boolean book(int start, int end) {
        Map.Entry pair = calendar.higherEntry(start);
        boolean res = end <= pair.getValue();
        if (res) calendar.put(end, start);
        return res;
    }
}

W/связанный список:

class ListNode {
    public int start, end;
    public ListNode next;
    public ListNode(int s, int e, ListNode n) {
        start = s;
        end = e;
        next = n;
    }
}

class MyCalendar {
    ListNode calendar;
    public MyCalendar() {
        ListNode tail = new ListNode(Integer.MAX_VALUE, Integer.MAX_VALUE, null);
        calendar = new ListNode(-1, -1, tail);
    }

    public boolean book(int start, int end) {
        ListNode curr = calendar, last = curr;
        while (start >= curr.end) {
            last = curr;
            curr = curr.next;
        }
        if (curr.start < end)
            return false;
        last.next = new ListNode(start, end, curr);
        return true;
    }
}

C ++ Код:

( Прыгните к : Описание задачи Идея решения )

class MyCalendar {
public:
    set> calendar = {{INT_MAX, INT_MAX}};
    bool book(int start, int end) {
        auto pair = calendar.upper_bound({start, end});
        bool res = end <= pair->second;
        if (res) calendar.insert({end, start});
        return res;
    }
};

W/связанный список:

struct LNode {
public:
    int start, end;
    LNode* next;

    LNode(int s, int e, LNode* n) {
        start = s;
        end = e;
        next = n;
    }
};

class MyCalendar {
public:
    MyCalendar() {
        LNode* tail = new LNode(INT_MAX, INT_MAX, nullptr);
        calendar = new LNode(-1, -1, tail);
    }

    bool book(int start, int end) {
        LNode* curr = calendar, *last = curr;
        while (start >= curr->end)
            last = curr, curr = curr->next;
        if (curr->start < end)
            return false;
        last->next = new LNode(start, end, curr);
        return true;
    }
private:
    LNode* calendar;
};

LeetCode Solutions (161 серия деталей)

Оригинал: “https://dev.to/seanpgallivan/solution-my-calendar-i-25dm”