Daily bit(e) C++. Объединение интервалов

Добавлено 30 сентября 2023 в 08:47

Daily bit(e) 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) 
{
    // Сортируем интервалы
    std::ranges::sort(intervals);

    std::vector<Interval> result;
    for (auto &interval : intervals)
    {
        if (result.empty() || result.back().end < interval.start)
        {   // У этого интервала нечем перекрывать,
            // или он не перекрывает предыдущий интервал.
            result.push_back(std::move(interval));
        }
        else
        {   // Этот интервал перекрывает предыдущий интервал.
            // Просто обновляем предыдущий интервал.
            result.back().end = std::max(result.back().end,
                                         interval.end);
        }
    }
    return result;        
}

Открыть решение на Compiler Explorer.

Решение

Теги