Существует ли полиномиальный алгоритм для нахождения назначения целых чисел интервалам?

У вас есть k машин и куча поступающих заданий (интервалов), каждое из которых имеет время начала и окончания. Каждое задание будет связывать машину на время своего временного интервала. Вы хотите узнать, справитесь ли вы со всеми заданиями.

Когда поступает задание, не имеет значения, какой машине вы его назначаете, важно только наличие незанятой машины. Точно так же не имеет значения, какие машины заняты, важно только, какие задания выполняются. Работа на машине 1, которая завершится через 2 часа, аналогична работе на машине 3, которая завершится через 2 часа; в любом случае, у вас занята машина на следующие два часа.

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

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

Это решается с помощью простого жадного алгоритма и двух стеков: одного из пар интервалов/целых чисел (изначально пустого) и одного из целых чисел (изначально заполненного от 0 до k).

Упорядочите интервалы по времени начала и повторите их. Для каждого интервала сначала выполните итерацию по стеку пар и извлеките каждый интервал со временем окончания, предшествующим времени начала текущего интервала. При извлечении интервалов соответствующее целое число помещается обратно в стек целых чисел. После этого извлеките одно целое число из целочисленного стека и поместите его вместе с текущим событием в парный стек.

Если в какой-то момент целочисленный стек иссякнет, проблема не имеет решения. Решением являются пары интервалов/целых чисел, когда вы помещаете их в стек.

Альтернативное решение, не имеющее максимального k, также простое: если стек целых чисел пуст, вы увеличиваете k и используете его вместо этого.

Если вы используете очередь с приоритетом по времени окончания для хранения пар интервал/целое число, этот алгоритм должен быть O(n log n) в худшем случае.

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

Судя по всему, более подробное обсуждение можно найти в следующем учебнике.

Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л.; Штейн, Клиффорд (2001) [1990]. Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03293-7.

Обратите внимание, что, согласно статье Википедии о раскраске графов, хроматическое число для интервальных графов равно клике количество.

Ваша задача эквивалентна поиску наибольшего количества пересекающихся интервалов, которые можно выполнить в O(nlogn).

Доказательство. Предположим, что для набора интервалов S k — это наибольшее количество пересекающихся интервалов из S. Ясно, что мы должны использовать по крайней мере k чисел для действительного присвоения. Теперь нам нужно показать, что k достаточно. Давайте переберем интервалы от S в порядке возрастания. Каждый раз, когда мы открываем новый интервал, мы выбираем число из набора неиспользованных чисел, и каждый раз, когда мы закрываем интервал, мы возвращаем число обратно в этот набор. Ясно, что для этого достаточно набора k чисел.

Код С++ для этого:

bool canAssign(const std::vector<std::pair<int, int>> &intervals, int k)
{
    const int left = 0, right = 1;

    std::vector<std::pair<int, int>> ends;
    for (const auto &interval: intervals)
    {
        ends.emplace_back(interval.first, left);
        ends.emplace_back(interval.second, right);
    }

    std::sort(ends.begin(), ends.end());

    int maxStack = 0, stack = 0;
    for (const auto &end: ends)
    {
        if (end.second == left)
            ++stack;
        else
            --stack;

        maxStack = std::max(maxStack, stack);
    } 

    return maxStack <= k;
}