Ежедневный бит (е) 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.