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

Question

У меня есть следующая проблема: задан ли список интервалов времени и целое число k, есть ли назначение значений <= k для интервалов, так что никакие два интервала, которые перекрываются, имеют одинаковое значение? Существует ли полиномиальный алгоритм для решения этой проблемы? Я думаю, что это можно решить с помощью динамического программирования, но я не могу придумать решение.

Answer 1

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

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

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

---

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

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

Answer 2

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

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

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

---

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

Answer 3

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

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

Cormen, Thomas H .; Leiserson, Charles E .; Ривест, Рональд Л. .; Stein, Clifford (2001) [1990]. Введение в алгоритмы (2-е изд.).MIT Пресса и Макгроу-Хилл. ISBN 0-262-03293-7.

Обратите внимание, что в соответствии с Wikipedia article на графике окрашивания хроматическое число для интервальных графов - это именно номер клики.

Answer 4

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

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

C++ код, который:

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; 
}