Вставка интервального диапазона с разделением на уникальные диапазоны

Question

Ищем идеи алгоритма, как вставить значение интервала, чтобы оно не перекрывало существующие интервалы.

Интервал диапазона сортируется от меньшего к большему [[0, 1], [3, 5]].

Теперь вставляем интервал диапазона [0, 7] в [[0, 1], [3, 5]] -> [[0, 1], [1, 3], [3, 5], [5, 7]] -> сгенерировано два новых диапазона, остальные остаются неизменными.

Вот еще один пример, вставка диапазона [-3, 5] в [[0, 1], [6,7]] -> [[-3, 0], [0, 1], [1, 5 ], [6, 7]]

Все языки программирования (особенно JavaScript) приветствуются, а также реализации псевдокодов.

Answer 1

в фактическом коде существует различие между старыми диапазонами интервалов и новыми диапазонами после применения определенной операции, эти диапазоны будут объединены вместе. Я хотел разделить вопрос на более мелкие части, чтобы исключить объединяющуюся часть.

Исключительно: проще объединить новый интервал напрямую, чем искусственно разделить его. Вот что я предлагаю ниже (C ++):

using DataType = /* whatever appropriate; double, int, unsigned int, ...*/;
using Interval = std::pair<DataType, DataType>;
std::vector<Interval> intervals;

void insert(Interval x)
{
    if(intervals.empty() || x.second < intervals.front().first)
    {
        intervals.insert(intervals.begin(), x); // (1)
    }
    else if(x.first > intervals.back().second)
    {
        intervals.push_back(x); // (2)
    }
    else
    {
        auto b = intervals.begin();
        while(b->second < x.first)
        {
            std::advance(b, 1);
        }
        // cannot be END iterator, otherwise would have been caught by (2)
        if(x.second < b->first)
        {
            // this is a new interval in between std::prev(b) and (b)
            intervals.insert(b, x);
        }
        else
        {
            // b is overlapping with x!
            if(b->first > x.first)
            {
                b->first = x.first;
            }

            auto e = std::next(b);
            while(e != intervals.end() && e->first <= x.second)
            {
                std::advance(e, 1);
            }
            // e is the first interval NOT overlapping with x!
            auto l = std::prev(e);
            b->second = std::max(x.second, l->second);
            // drop all subsequent intervals now contained in b (possibly none)
            intervals.erase(std::next(b), e);
        }
    }
}

Только алгоритм, сэкономил усилия по упаковке в класс, имея удобную функцию, принимающую маркеры начала / конца (вместо интервала), ...

Если тип данных, который вы намереваетесь использовать, не предоставляет обратный метод доступа (C ++: например, std::forward_list): нет проблем, просто отбросьте второй if (содержащий (2)); тогда, однако, b может быть конечным итератором, так что вам придется проверять, и если тест пройден успешно, вы можете вставить его в конце. Скорее всего, тогда у вас не было бы «вставки раньше», поэтому вам придется отдельно отслеживать предшественников b и более поздних версий e ...