Блог

У нас есть n элементов, входящих и выходящих из очереди, они могут входить и выходить в любое время. Информация,которой мы располагаем, заключается в том, что для каждой пары (a, b) мы знаем либо 1) a покидает очередь до того, как входит b, либо наоборот; 2) в какой-то момент a и b находятся в очереди одновременно. или 3) никакой информации вообще. Предположим, нам дан список попарной информации для всех (n выберите 2) пар, найдите алгоритм O(n^2), чтобы определить, есть ли какая-либо несогласованность в информации.

Например, a уходит до того, как b входит(для простоты запишите его как a>b), b>>c, и c=a несовместимо, так как нет возможной временной шкалы a,b,c для входа и выхода из очереди, которая делает все три утверждения истинными. Я думал о том, чтобы сделать это проблемой пересечения графа, каждый элемент как вершина, попарное отношение как ребро, если a>b или b> Однако это не просто какой-либо цикл приводит к несогласованности, очевидно, что если все ребра в цикле направлены, то это точно несогласованно, как > или > Однако, если все ребра в цикле неориентированы, несогласованности нет. Или, если некоторые из них направлены, а некоторые не направлены, могут быть либо непоследовательными, либо последовательными. Например, a>b, b>>c и c=a несовместимы, в то время как a=b,b=c и c>>>a согласованы.

Любой вклад и идея будут высоко оценены!

Думайте об этом как об орграфе, где есть дуга от a до b , если a уходит до b входа, и наоборот.

Для узлов (x,y), которые одновременно находятся в очереди, обратите внимание, что это означает, что для каждой вершины w согласованный граф не имеет x < w < y, а также не имеет x > w < y, а также не имеет x >> y. Отразите это, объединив такие узлы в один узел, сохранив все дуги.

Затем выполните топологическую сортировку, чтобы найти топологическое упорядочение узлов.

Существует несоответствие тогда и только тогда, когда нет топологического порядка.

Время выполнения: сортировка топо равна O(узлы ребра), что равно O(n^2).