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