Ежедневный бит (е) C++ # 37, Общая проблема интервью C++: непокрытые интервалы

Сегодня мы рассмотрим распространенную проблему интервью C++: непокрытые интервалы.

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

Интервалы полуоткрытые, т. е. интервал {10, 15} покрывает 10, 11, 12, 13 и 14 (не 15).

В качестве дополнительной (специфической для C++) задачи избегайте ненужных копий входных данных.

Прежде чем продолжить чтение решения, попробуйте решить его самостоятельно. Вот ссылка на Compiler Explorer с парой тестов: https://compiler-explorer.com/z/3zj4M4hW7.

Решение

Мы уже сортируем каждое расписание и не пересекаемся, что значительно упрощает задачу.

Итак, когда у нас есть непокрытый интервал? Если мы обрабатываем интервалы в порядке их начала и отслеживаем самое позднее окончание, у нас будет непокрытый интервал, если текущее время начала больше, чем самое позднее время окончания. Тогда разрыв будет просто {latest end, current start}.

Используя приоритетную очередь, мы можем выбрать интервал с наименьшим временем начала в log(K), где K — количество расписаний. Однако есть проблема. Очередь с приоритетом не позволяет эффективно извлекать элементы; следовательно, у нас возникнут копии данных. Есть несколько способов обойти эту проблему. Здесь мы используем алгоритмы кучи, которые работают точно так же, как приоритетная очередь, но поверх любого контейнера с произвольным доступом.

Есть одна последняя проблема. По мере обработки каждого расписания нам нужно удалять элементы из начала расписания (по мере того, как мы выходим за этот интервал). К сожалению, это операция O(n) для std::vector, поэтому нам нужен обходной путь. Вместо того, чтобы работать с вводом напрямую, мы можем обернуть каждое расписание в файл std::span. std::span — это облегченная оболочка в стиле представления для смежных данных с дешевым созданием подпредставления, не содержащего первого элемента.

struct Interval {
    int start;
    int end;
};

std::vector<Interval> uncovered(
  const std::vector<std::vector<Interval>>& schedule) {
    if (schedule.empty()) return {};
    std::vector<Interval> result;

    // We will need to erase from the front of each schedule, 
    // which is a O(n) operation for std::vector. 
    // Adapting the schedule to std::span fixes this without
    // introducing copies.
    std::vector<std::span<const Interval>> adapted(
      schedule.begin(), schedule.end());
  
    // Comparison to put the earliest start schedule first.
    auto cmp = [](const auto& left, const auto& right) {
        return left.front().start > right.front().start;
    };
  
    // Using heap algorithms instead of a std::priority_queue
    // to avoid copies.
    std::make_heap(adapted.begin(), adapted.end(), cmp);
  
    // Since we ignore infinite intervals, our start is with the end 
    // of the earliest interval.
    int earliest_start = adapted.front().front().end;
  
    // Process each interval, in the order of their start times.
    while (!adapted.empty()) {
        // If the current interval starts after our earliest start, 
        // we know that that the time in-between is uncovered.
        if (adapted.front().front().start > earliest_start)
            result.push_back(
            Interval{earliest_start, 
                   adapted.front().front().start});

        // Update earliest start (we only sort by start, 
        // so we must use max)
        earliest_start = std::max(
          earliest_start, adapted.front().front().end);

        // Pop will move the top element to the back.
        std::pop_heap(adapted.begin(), adapted.end(), cmp);
      
        // Shorten the schedule by the first element.
        adapted.back() = adapted.back().subspan(1);
      
        // If it's empty, then kick it out completely, if not, 
        // push it back into the heap.
        if (adapted.back().empty()) {
            adapted.pop_back();
        } else {
            std::push_heap(adapted.begin(), adapted.end(), cmp);
        }
    }
    return result;
}

Откройте решение в Compiler Explorer.