Взятие пар чисел, представляющих начало / конец, и удаление наложений

Question

У меня есть массив пар, которые представляют диапазон [начало, конец).Можно предположить, что массив уже отсортирован по полю 'begin'.

Я хочу создать новый массив с удалением всех перекрытий и созданием дополнительных пар, если необходимо.

ДляНапример, допустим, что массив содержал следующие пары:

[1,3],[2,5],[7,15],[8,9],[12,19]

Выходные данные должны быть следующими:

[1,2],[2,3],[3,5],[7,8],[8,9],[9,12],[12,15],[15,19]

В конечном итоге выходной массив не должен содержать перекрытий вообще.

Какое наиболее оптимальное решение требует не более O (m), где m - количество записей, необходимых в выходном массиве?Я думаю, что я вижу способ сделать это в O (n ^ 2), где n - это число записей во входном массиве, но должен быть лучший способ.

Окончательная реализация будет вC ++ 11, использующий векторы пар двойников, хотя решения с псевдокодом хороши.

РЕДАКТИРОВАТЬ:

Я ценю все ответы, но я вежливо просил бы заранее, чтобы не публиковать какие-либо решениякоторые зависят от конкретных фреймворков или библиотек, если только такие фреймворки не являются частью стандарта c ++ 11.

Answer 1

Сначала я решу связанную проблему;генерировать объединенные интервалы, которые покрывают одну и ту же область без смежности или перекрытия.

Пройдите по входному массиву.Начните с первого элемента.Запишите верхнюю (конец интервала) и нижнюю (начало интервала).

Перейдите вперед.Каждый элемент, если он перекрывает интервал, простирается высоко над водой.Если нет, выведите highwater и lowater как интервал, а затем запишите новый high и lowater.

Это займет O (n) время на входе.

Каждый элемент ввода должен быть прочитан, потому чтолюбой из них может перейти от своего начального местоположения к концу и изменить результат.Так что это O-оптимально.

---

Это объединяет интервалы в самый большой непрерывный, который вы можете сделать;Вы хотите сохранить все «края» или «швы» в исходных интервалах.Чтобы решить ваши задачи, просто следите за швами (по порядку) и разрывайте сгенерированные интервалы на этих швах.«Низкие» швы всегда будут иметь растущие значения;швы с высокой водой не могут.Так что заказанный набор швов должен работать.К сожалению, это O (nlgn) из-за сета.

---

// half open
struct interval {
    int lowater = 0;
    int highwater = 0;
    bool empty() const {
        return lowater == highwater;
    }

    friend std::ostream& operator<<( std::ostream& os, interval i ) {
        return os << "[" << i.lowater << "," << i.highwater << "]";
    }
};


template<class Range, class Out>
void build_intervals( Range&& in, Out out ) {
    std::optional<interval> current;
    std::set<int> seams;

    auto dump_interval = [&](interval i){
        if (i.empty()) return;
        *out = i;
    };
    auto dump_current = [&]{
        if (!current) return;

    //    std::cout << "Dumping " << *current << " with seams: {";
        for (int seam:seams) {
    //        std::cout << seam << ",";
            dump_interval({ current->lowater, seam });
            current->lowater = seam;
        }
    //    std::cout << "}\n";
        dump_interval( *current );
        current = std::nullopt;
        seams.clear();
    };
    for (auto&& e : in) {
        if (current && e.lowater <= current->highwater) {
            seams.insert(e.lowater);
            seams.insert(e.highwater);
    //        std::cout << "No gap between " << *current << " and " << e << "\n";
            current->highwater = (std::max)(e.highwater, current->highwater);
    //        std::cout << "Combined: " << *current << "\n";
            continue;
        }
        if (!current) {
    //        std::cout << "New current " << e << "\n";
        } else {
    //        std::cout << "Gap between " << *current << "  and " << e << "\n";
            dump_current();
        }
        current = e;
        seams.insert(e.lowater);
        seams.insert(e.highwater);
    }
    dump_current();
}

живой пример .

Answer 2

Я придумал что-то вроде этого, добавив всего пару слов, если это сделано за O (n) раз.Я просто не уверен насчет последних элементов, мой вывод:

[1 : 2], [2 : 3], [3 : 5], [7 : 8], [8 : 9], [9 : 12], [12 : 15], [15 : 19]

Может быть, это то, что поможет:

std::vector<std::pair<int, int>> noOverlaps(std::vector<std::pair<int, int>>& input) {
    if (input.size() <= 1) {
        return input;
    }
    std::vector<std::pair<int, int>> result;
    result.push_back(input[0]);

    for (int i = 1; i < input.size(); ++i) {
        //If overlap
        if (input[i].first < result.back().second) {
            auto lastOne = result.back();
            result.pop_back();
            result.push_back(std::make_pair(lastOne.first, input[i].first));
            if (lastOne.second > input[i].second) {
                result.push_back(std::make_pair(input[i].first, input[i].second));
                result.push_back(std::make_pair(input[i].second, lastOne.second));
            } else {
                result.push_back(std::make_pair(input[i].first, lastOne.second));
                result.push_back(std::make_pair(lastOne.second, input[i].second));
            }
        } else {
            result.push_back(input[i]);
        }
    }
    return result;
}

Обновление 1 Как указано вПриведенный выше комментарий не будет работать с несколькими перекрывающимися интервалами, поэтому вышеприведенное решение можно улучшить, проглотив интервалы, которые содержат друг друга и работают по одному и тому же алгоритму:

std::vector<std::pair<int, int>> noOverlaps(std::vector<std::pair<int, int>>& origInput) {
    if (origInput.size() <= 1) {
        return origInput;
    }
    std::vector<std::pair<int, int>> result;
    std::vector<std::pair<int, int>> input;
    input.push_back(origInput[0]);

    for (int i = 1; i < origInput.size(); ++i) {
        if (input[i-1].first <= origInput[i].first && input[i-1].second >= origInput[i].second) {
            continue;
        }
        input.push_back(origInput[i]);
    }

    result.push_back(input[0]);

    for (int i = 1; i < input.size(); ++i) {
        //If overlap
        if (input[i].first < result.back().second) {
            auto lastOne = result.back();
            result.pop_back();
            result.push_back(std::make_pair(lastOne.first, input[i].first));
            if (lastOne.second > input[i].second) {
                result.push_back(std::make_pair(input[i].first, input[i].second));
                result.push_back(std::make_pair(input[i].second, lastOne.second));
            } else {
                result.push_back(std::make_pair(input[i].first, lastOne.second));
                result.push_back(std::make_pair(lastOne.second, input[i].second));
            }
        } else {
            result.push_back(input[i]);
        }
    }
    return result;
}

Но для этого требуется 2xO (n) сложность пространстваи код не очень хороший.

Так что мне просто интересно, не будет ли этого достаточно:

std::vector<std::pair<int, int>> noOverlaps2(std::vector<std::pair<int, int>>& origInput) {
    if (origInput.size() <= 1) {
        return origInput;
    }
    int low = origInput[0].first, high = origInput[0].second;
    std::vector<std::pair<int, int>> result;

    for (int i = 1; i < origInput.size(); ++i) {
        if (high < origInput[i].first) {
            result.emplace_back(low, high);
            low = origInput[i].first;
            high = origInput[i].second;
        } else {
            high = std::max(origInput[i].second, high);
        }
    }
    result.emplace_back(low, high);

    return result;
}

Для ваших данных он выдает: [1 : 5], [7 : 19], но избавляется от наложений.