Сложность: medium
Вам дан массив из 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⃣Переберите отсортированные пары и выберите пары, которые могут следовать одна за другой, увеличивая длину цепочки.
😎 Решение:
def findLongestChain(pairs):
pairs.sort(key=lambda x: x[1])
current_end = float('-inf')
count = 0
for pair in pairs:
if current_end < pair[0]:
current_end = pair[1]
count += 1
return count
Ставь 👍 и забирай 📚 Базу знаний