Разбор задачи 646. Maximum Length of Pair Chain с Литкода

646. Maximum Length of Pair Chain

Условие

Дан массив из n пар pairs гдеpairs[i] = [lefti, righti] и lefti < righti.

Пара p2 = [c, d] следует за парой p1 = [a, b] если b < c. Таким образом можно сформировать цепочку пар.

Верни длину самой длинной цепочки, которая может быть сформирована.

Вам не обязательно использовать все заданные интервалы. Вы можете выбирать пары в любом порядке.

Пример 1:

Ввод: pairs = [[1,2],[2,3],[3,4]]
Вывод: 2
Объяснение: Самая длинная цепочка [1,2] -> [3,4].

Пример 2:

Ввод: pairs = [[1,2],[7,8],[4,5]]
Вывод: 3
Объяснение: Самая длинная цепочка [1,2] -> [4,5] -> [7,8].

Ограничения:

• n == pairs.length
• 1 <= n <= 1000
• -1000 <= lefti < righti <= 1000

Решение

Итак, представим наши пары в виде графа, где вершина - это одна пара, и две вершины соединяются ребром, если две пары могут образовать цепочку. То есть, если есть пары pair1 и pair2 и pair1[1] < pair2[0], то будет ребро от pair1 до pair2.
Например, массив [[1,2],[7,8],[4,5]]

Далее я буду употреблять слова "пара" и "вершина" как синонимы.
Если мы будем отмечать у каждой вершины длину максимальной цепочки, которая оканчивается этой вершиной, то следующуя вершина будет иметь длину цепочки + 1:

Если две цепочки с длинами N и M оканчиваются на двух вершинах, и у этих двух вершин один и тот же сосед, то чтобы составить максимальную цепочку, нужно выбрать цепочку с наибольшей длиной:

Кажется можно сделать такой алгоритм:

1. Пометить все вершины единицами (цепочка из одной вершины всегда есть).
2. Пройтись по всем вершинам:
• У каждой вершины взять длину цепочки, которая у неё сейчас (длину цепочки, которая оканчивается этой вершиной).
• Пройтись по соседям вершины. Каждому соседу проставить длину цепочки + 1, если у соседа длина его текущей цепочки (цепочки, которая оканчивается этим соседом) меньше чем длина цепочки взятой вершиы + 1

Но этот алгоритм обламывается на таком случае, когда у нас есть массив
[[4,5], [7,8],[1,2]]
Мы сначала возьмем вершину [4,5] возьмем её длину (изначально у всех по единице). Пройдем от неё к соседу [7,8], поставим соседу длину + 1, то есть 2.
Потом возьмем вершину [7,8] от неё нет никаких вершин дальше, потому что нет пары, у которой первый элемент больше 8. Потом пройдем к паре [1,2] от неё перейдем к соседу [4,5], и проставим соседу длину 2. Получится, что максимальная длина равна якобы 2, хотя она на самом деле 3.
[[1,2],[4,5],[7,8]].
Порядок обхода имеет значение. Если мы начинаем с вершины A, мы должны быть уверены, что сейчас у вершины максимальная длина цепочки, которая на ней оканчивается. Если длина цепочки у вершины поменялась, то надо перестроить всех соседей, соседей соседей, и т.д. дальше. Если мы посмотрим на ограничения к задаче, то увидим, что у pair[lefti, righti] lefti < righti.
Если мы отсортируем массив по первому или последнему элементу пары, то мы гарантировано будем начинать с пары, у которой не будет другой пары, которая могла бы стоять перед ней, и если на очередной итерации мы перешли к новой паре, то в этот момент у неё уже будет максимальная вершина.

Итак, алгоритм дополняется сортировкой:

1. Отсортировать массив пар (по первому или последнему числу в паре).
2. Пометить все вершины единицами (цепочка из одной вершины всегда есть).
3. Пройтись по всем вершинам:
• У каждой вершины взять длину цепочки, которая у неё сейчас (длину цепочки, которая оканчивается этой вершиной).
• Пройтись по соседям вершины. Каждому соседу проставить длину цепочки + 1, если у соседа длина его текущей цепочки (цепочки, которая оканчивается этим соседом) меньше чем длина цепочки взятой вершиы + 1

Кстати, наш алгоритм прохода немного похож на Алгоритм Дейкстры, только там вычисляется длина минимальной цепочки, а здесь максимальной.

Нужно ли строить реальный граф? Заводить класс для вершины, ссылку на соседей? Необязательно.
Можно воспользоваться одномерным массивом dp (dynamic programming)
dp[i] будет содержать длину цепочки, которая оканчивается парой i (в уже отсортированном массиве).
Итак, сортируем массив.
Создаем массив dp и заполняем его единицами (цепочки из одной вершины).
Проходим по исходному уже отсотированному массиву, идем от каждой пары правее и смотрим соседей. Сосед проверяетя if'ом pairs[j][0] > pairs[i][1].
Если вершина является соседом, то выставляем соседу текущую длину + 1, если текущая длина + 1 больше чем та длина, которая записана у соседа сейчас.
Попутно сразу считаем максимальную длину.

Полный код такой:

public class Solution {  
    public int FindLongestChain(int[][] pairs) {
        Array.Sort(pairs, (a, b) => a[0].CompareTo(b[0]));
        var dp = new int[pairs.Length];
        Array.Fill(dp, 1);
        var max = 1;
        for (var i = 0; i < dp.Length; i++)
        {
            for (var j = i + 1; j < dp.Length; j++)
            {
                if (pairs[j][0] > pairs[i][1])
                {
                    dp[j] = Math.Max(dp[j], dp[i] + 1);
                    max = Math.Max(max, dp[j]);
                }
            }
        }
        
        return max;
    }
}