Можно ли выбрать число из каждого интервала без повторения в выборе. Решение в ЛИНЕЙНОМ ВРЕМЕНИ

Question

Я пробовал этот вопрос по практике хакер-арта, которая требует ниже работы.

ПРОБЛЕМА

Дано целое число п, которое означает последовательность п чисел от {0,1,2,3,4,5 ....... N-2, N-1}

Мы предусмотрены м диапазоны в виде (L, R) такой, что (0 < = L < = п-1) (0 < = R < = п-1)

, если (L < = R), (L, R) обозначает числа {L, L + 1, L + 2, L + 3 ....... R-1, R} из приведенной выше последовательности

els e (L, R) обозначает числа {R, R + 1, R + 2, ....... n-2, n-1} & {0,1,2,3 .... L-1 , L} т.е. число обтекать

примера

n = 5 ie {0,1,2,3,4} 
(0,3) signifies {0,1,2,3} 
(3,0) signifies {3,4,0} 
(3,2) signifies {3,4,0,1,2} 

Теперь мы должны выбрать один (только один) номер из каждого диапазона без повторения какого-либо выбора. Мы должны сказать, что можно выбрать один номер из каждого (и каждого) диапазона без повторения.

Пример тест

n = 5// numbers {0,1,2,3,4} 
// ranges m in number // 
0 0 ie {0} 
1 2 ie {1,2} 
2 3 ie {2,3} 
4 4 ie {4} 
4 0 ie {4,0} 

Answer is "NO" it's not possible. 

Поскольку мы не можем выбрать любое число из диапазона 4 0, потому что, если мы выбираем 4 из него мы не могли быть в состоянии выбрать из диапазона 4 4 и если выбрать 0 из нее мы бы не быть в состоянии выбрать из 0 0

Мои подходы -

1) это может быть сделано в O (N * M) с помощью проверки всех возможностей прибора отбора из каждого диапазона и бок о бок, используя хэш-карту recurrsion запишите наши выборы.

2) Я пробовал его в порядке n или m, т.е. линейный заказ. Проблема не имеет редакционного объяснения. Только код упоминается в редакционной статье без комментариев и объяснений. Я не могу получить код кодового словаря кем-либо, который передает все тестовые примеры и получил одобрение.

Я не могу понять логику/алгоритм, используемый в коде и почему он работает?

Пожалуйста, предложите любой линейный метод и логику, потому что проблема имеет следующие ограничения

1 <= N<= 10^9 
    1 <= M <= 10^5 
    0 <= L, R < N 

, который требует линейную или NlogN решение, как я догадываюсь ??

Код в редакции также можно увидеть здесь http://ideone.com/5Xb6xw

Предупреждение --after ищет код, который я нашел код, используя п и м interchangebly Поэтому я хотел бы упомянуть формат ввода для этой проблемы.

Входной формат

Первая строка содержит тестовые случаи, тк, за которыми следуют два целых числа N, M- первый изображающую число стран на земном шаре, второй изображающая количество диапазонов его подруга ему дали.После этого следующие M строк будут иметь два целых числа, описывающих диапазон, X и Y. Если (X < = Y), то диапазон охватывает страны [X, X + 1 ... Y], другие диапазоны охватывает [X, X + 1, ... N-1,0,1 ..., Y].

Формат вывода

Print «YES», если это можно сделать так, печать «НЕТ», если это не так.

Answer 1

Существует два компонента редакционного решения.

уменьшение линейного времени к задаче на обычных интервалах

Предположит, чтобы избежать тривиальных случаев, что число входных интервалов меньше, чем п.

Первый заключается в том, чтобы уменьшить проблему до того, где интервалы не обертываются следующим образом. Учитывая интервал [L, R], если L ≤ R, затем испускаем два интервала [L, R] и [L + n, R + n]; если L> R, испустите [L, R + n]. Легкое направление сокращения показывает, что если исходная задача имеет решение, то приведенная задача имеет решение. Для [L, R] с L ≤ R задано число k, присваиваем k [L, R] и k + n равным [L + n, R + n]. Для [L, R] с L> R назначьте любое из k, k + n принадлежит [L, R + n]. За исключением двойного назначения k и k + n для интервалов [L, R] и [L + n, R + n] соответственно, каждый интервал получает свой собственный класс вычетов mod n, поэтому присваивания не конфликтуют.

И наоборот, жесткое направление редукции (если исходная проблема не имеет решения, то приведенная проблема не имеет решения) доказана с использованием Hall's marriage theorem. По критерию Холла неразрешимая исходная задача имеет для некоторого k набор из k входных интервалов, объединение которых имеет размер меньше k. Сначала мы утверждаем, что существует такой набор входных интервалов, объединение которых является (круговым) интервалом (который по предположению не является всем 0..n-1). Разложите союз на множество максимальных (круговых) интервалов, которые его составляют. Каждый интервал ввода содержится в одном из этих интервалов. Посредством аргумента усреднения некоторый максимальный (круговой) интервал содержит больше входных интервалов, чем его размер. Мы заканчиваем тем, что «поднимаем» этот контрпример к уменьшенной задаче. Учитывая максимальный (круговой) интервал [L *, R *], поднимем его на обычный отрезок [L *, R *], если L * ≤ R * или [L *, R * + n], если L *> Р*. Точно так же с круглыми интервалами, содержащимися в этом интервале. Довольно утомительно, но просто показать, что этот поднятый контрпример удовлетворяет критерию Холла, что означает, что приведенная задача не имеет решения.

O (м лога м) -time решения для обычных интервалов

Это алгоритм развертки строки. Сортируйте интервалы по нижней конечной точке и сканируйте их в указанном порядке. Мы представляем, что линия развертки перемещается от нижней конечной точки к нижней конечной точке. Поддерживайте набор интервалов, которые пересекают линию развертки и не имеют номера, отсортированные по верхней конечной точке. Когда линия развертки собирается двигаться, назначьте числа между старым и новым положениями интервалами в наборе, преимущественно теми, чья верхняя конечная точка является самой низкой. Правильность этой стратегии должна быть ясной: интервалы, которым может быть присвоено число, но переданы, имеют по меньшей мере так много опций (в смысле того, что они являются суперсет) в качестве интервалов, которые назначены, поэтому мы никогда не делаем выбор, который у нас есть причина сожаления.