Ежедневная часть C++ № 233, Распространенная задача собеседования по C++: объединение интервалов.
Сегодня мы рассмотрим распространенную проблему интервью C++: объединение интервалов.
Учитывая список потенциально перекрывающихся интервалов (начало и конец представлены целыми числами), объедините все перекрывающиеся интервалы и верните результирующий список непересекающихся интервалов.
Интервалы {a,b}, {b,c} считаются перекрывающимися.
Например, для ввода {{2,3},{0,1},{2,4},{1,2} вывод должен быть {{0,4} .
Прежде чем продолжить чтение, я советую вам попытаться решить эту проблему самостоятельно. Вот ссылка на Compiler Explorer с парой тестовых примеров: https://compiler-explorer.com/z/3GhjWrG6b.
Решение
Когда мы рассматриваем два интервала, они будут находиться в одной из следующих трех конфигураций:
- Они не перекрываются: один интервал находится строго перед другим.
- Они полностью перекрываются: один интервал находится строго внутри другого.
- Они частично перекрываются: только конец одного интервала находится внутри другого.
Рассмотрение всех этих вариантов было бы довольно трудоемким. Поэтому мы хотим устранить некоторую сложность и придать интервалам некоторый порядок (т. е. отсортировать их).
Если мы отсортируем интервалы по их началу, нам нужно будет учитывать перекрытия только в одном направлении. Это дает нам более простую логику объединения двух перекрывающихся интервалов: {first.start, std::max(first.end, Second.end), т. е. если два соседних интервала перекрываются, у нас есть только учитывать время окончания, поскольку время начала уже было неявно определено при сортировке.
Кроме того, как только мы объединяем интервал, он остается в правильном отсортированном положении. Таким образом, мы можем обработать весь ввод за один проход, обновляя последний интервал, пока существует перекрытие, и в противном случае вставляя интервалы без изменений, если они не перекрываются.
std::vector<Interval> merge_intervals(
std::vector<Interval>& intervals) {
// Sort the intervals
std::ranges::sort(intervals);
std::vector<Interval> result;
for (auto &interval : intervals)
// This interval has nothing to overlap
// with or doesn't overlap.
if (result.empty() || result.back().end < interval.start)
result.push_back(std::move(interval));
// This interval overlaps.
// Only update the previous interval.
else
result.back().end = std::max(result.back().end,
interval.end);
return result;
}
