Сложность: 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⃣Переберите отсортированные пары и выберите пары, которые могут следовать одна за другой, увеличивая длину цепочки.
😎 Решение:
public class Solution {
public int FindLongestChain(int[][] pairs) {
Array.Sort(pairs, (a, b) => a[1] - b[1]);
int currentEnd = int.MinValue;
int count = 0;
foreach (var pair in pairs) {
if (currentEnd < pair[0]) {
currentEnd = pair[1];
count++;
}
}
return count;
}
}Ставь 👍 и забирай 📚 Базу знаний