Задача: 732. My Calendar III
Сложность: hard

k-бронирование происходит, когда k событий имеют некоторое непустое пересечение (т.е, дано некоторое время, общее для всех k событий). Даны некоторые события [startTime, endTime), после каждого данного события верните целое число k, представляющее максимальное k-бронирование между всеми предыдущими событиями. Реализация класса MyCalendarThree: MyCalendarThree() Инициализирует объект. int book(int startTime, int endTime) Возвращает целое число k, представляющее наибольшее целое число, при котором в календаре существует k-бронирование.

Пример:

Input
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, 1, 1, 2, 3, 3, 3]

👨‍💻 Алгоритм:

1⃣Создайте два словаря для хранения изменений времени бронирования: один для начала событий, другой для конца событий.

2⃣Для каждого нового события обновите словари начала и конца событий.

3⃣Поддерживайте текущее количество активных бронирований и обновляйте максимальное количество активных бронирований по мере добавления новых событий.

😎 Решение:

using System;
using System.Collections.Generic;

public class MyCalendarThree {
    private SortedDictionary<int, int> events;

    public MyCalendarThree() {
        events = new SortedDictionary<int, int>();
    }

    public int Book(int startTime, int endTime) {
        if (!events.ContainsKey(startTime)) {
            events[startTime] = 0;
        }
        if (!events.ContainsKey(endTime)) {
            events[endTime] = 0;
        }
        events[startTime]++;
        events[endTime]--;
        
        int active = 0;
        int maxActive = 0;
        foreach (var count in events.Values) {
            active += count;
            maxActive = Math.Max(maxActive, active);
        }
        
        return maxActive;
    }
}

Ставь 👍 и забирай 📚 Базу знаний