Вам даны пары чисел
n. В каждой паре первое число всегда меньше второго. Пара(c,d)может следовать за(a,b)тогда и только тогда, когдаbменьшеc. Цепи пар могут быть сформированы таким образом. Найдите самую длинную цепочку образованных пар.
Я получил этот вопрос в интервью Amazon, но не смог понять ответ, просто потому, что он связан с проблемой LIS.
Поскольку два значения каждой пары (X, Y) должны быть в порядке (X < Y), а значение Y одной пары должно быть меньше значения X следующей пары, вы, по существу, строите один непрерывная цепочка значений вдоль одного измерения. Вам просто нужно отсортировать по значениям Y.
Учитывая данные примера:
(15,40) (5,8) (1,10) (6,8) (9,20) (2,4) (36,37) (34,35) (9,14) (30,31)
Сортировать по Y, чтобы получить:
(2,4) (6,8) (5,8) (1,10) (9,14) (9,20) (30,31) (34,35) (36,37) (15,40)
Затем проведите цикл, добавив пару в цепочку, если ее X больше последнего Y в цепочке и игнорирует его в противном случае.
Обратите внимание, что в этом примере (6,8) удалось отсортировать до (5,8). Не имеет значения, какая пара выбрана для цепочки, когда их значения Y равны, если значение X удовлетворяет условию превышения предыдущего Y.
Здесь показана диаграмма, в которой сортированные пары находятся в виде столбцов над числовой строкой. Начиная с первой пары, (2,4), каждый, добавленный к цепочке внизу, окрашен в желтый цвет. Визуально серые пропускаются, потому что там желтый цвет "на пути" его падает в цепочку (перекрывающиеся значения).
Доказательство: Единственный способ включить большее количество пар в цепочку - заменить пару на одну с меньшим значением Y, чтобы позволить следующей паре иметь меньшее значение X, потенциально подходящую другую пару, где она не могла соответствовать раньше. Если вы замените пару на одну с тем же значением Y, вы ничего не получите. Если замена имеет большее значение Y, все, что вы сделали, потенциально блокирует некоторые пары, которые были бы подобраны раньше.
Поскольку пары были отсортированы по значению Y, вы никогда не найдете замену меньшим Y. Глядя на "вперед" в отсортированных парах, все они будут иметь одинаковое или большее значение Y. Глядя "назад", все, которые были исключены из цепочки изначально, были связаны с тем, что значение X было недостаточно высоким, что будет по-прежнему иметь место.
Мы можем начать с подхода Брайана, сортируя все пары на основе значения y. Он обеспечит требуемое условие предыдущей пары X < следующая пара y. Теперь нам нужна самая длинная возрастающая подпоследовательность x среди нового списка пар. Который мы можем получить, сортируя все x и находим самую длинную общую подпоследовательность между отсортированным x и новым ранее созданным списком
Во-первых, эту проблему можно рассматривать как график точек на двумерной сетке, где координата x каждой точки меньше y координаты этой точки. Теперь вас попросят найти самую длинную цепочку так, чтобы каждая я + 1-я точка была выше и справа от i-й точки (а координата y i-й точки меньше x координаты я + 1-й пункт).
теперь можно отсортировать точки сначала на основе их координаты x. Затем мы начинаем посещать отсортированные точки с наименьшей координаты x, если есть связь для x координаты, тогда мы сначала наберем точки с более высокой координатой y. теперь, например, если мы работаем над i-й точкой, мы знаем, что все точки, которые уже были посещены, имеют меньшую или аналогичную координату x i-го. Таким образом, самый длинный конец цепи в точке я будет самой длинной цепью, которую мы уже получили с координатой y <= x текущей точки.
Мы можем сделать это эффективно с помощью эффективной структуры данных, такой как дерево сегментов или двоичное индексированное дерево.
Время выполнения этого решения: O (NlgN), где N - количество точек (пары в заданной задаче).
Основным способом решения этой проблемы было бы создание дерева, где каждая node является парой, и конструирует направленные ребра из одного node в другой, когда он является законным (т.е. пара A (c, г) может следовать (а, Ь) тогда и только тогда, когда Ь меньше с "). Вы можете сделать первый шаг по ширине из каждого node, который отслеживает длину самого длинного пути из этого node, и когда вы закончите с этим, можете просто просмотреть все узлы, чтобы найти самый длинный путь.
Мне кажется, что одна из характеристик самой длинной цепи состоит в том, что она минимизирует общий диапазон любых двух соседних кортежей (чтобы максимизировать количество возможных кортежей для любого диапазона).
В этом случае, как предложил Брайан Стивенс, нам нужно сортировать только по второму числу, по возрастанию (чтобы гарантировать наименьший интервал при поиске следующего кортежа) и построить цепочку, начиная с первого кортежа в отсортированном списке.
Мы можем доказать, что это решение оптимально, полагая, что если S (0) - цепочка, начинающаяся с первого набора, существует S (i), где я не находится в S (0), что больше, чем S (0); и, следовательно, также цепь S (i + 1), которая длиннее S (1). Мы знаем, что начало я должно быть до конца i-1 или оно было бы включено в S (0). Теперь, если конец i-1 был равен концу i, S (i + 1) будет частью S (0), что противоречит нашей предпосылке. В качестве альтернативы, если конец я был больше конца i-1, снова S (i + 1) будет включен в S (0). Конец я не может быть меньше конца i-1, так как список сортируется по этому свойству.