#ЛитКод
Задача: 646. Maximum Length of Pair Chain

Вам дан массив из n пар, где pairs[i] = [lefti, righti] и lefti < righti. Пара p2 = [c, d] следует за парой p1 = [a, b], если b < c. Таким образом можно построить цепочку пар. Верните самую длинную цепочку, которую можно составить. Вам не нужно использовать все заданные интервалы. Вы можете выбирать пары в любом порядке.

Пример:

Input: nums = [1,2,2,4]
Output: [2,3]

👨‍💻 Алгоритм:

1⃣Отсортируйте пары по второму элементу каждой пары (righti).
2⃣Используйте динамическое программирование или жадный алгоритм, чтобы построить цепочку максимальной длин
3⃣Переберите отсортированные пары и выберите пары, которые могут следовать одна за другой, увеличивая длину цепочки.

😎 Решение:

fun findLongestChain(pairs: Array<IntArray>): Int {
    pairs.sortBy { it[1] }
    var currentEnd = Int.MIN_VALUE
    var count = 0
    for (pair in pairs) {
        if (currentEnd < pair[0]) {
            currentEnd = pair[1]
            count++
        }
    }
    return count
}

👉Новости 👉Платформа