646. Maximum Length of Pair Chain

leetcode medium

#array#csharp#dynamic-programming#graph#greedy#intervals#leetcode#medium#search#sort#two-pointers

Task

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

Пример:

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

Output: [2,3]

C# solution

matched/original

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;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    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;
    }
}

Java solution

matched/original

import java.util.Arrays;

class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> a[1] - b[1]);
        int currentEnd = Integer.MIN_VALUE;
        int count = 0;
        for (int[] pair : pairs) {
            if (currentEnd < pair[0]) {
                currentEnd = pair[1];
                count++;
            }
        }
        return count;
    }
}

JavaScript solution

matched/original

function findLongestChain(pairs) {
    pairs.sort((a, b) => a[1] - b[1]);

    let currentEnd = Number.MIN_SAFE_INTEGER;
    let count = 0;

    for (const pair of pairs) {
        if (currentEnd < pair[0]) {
            currentEnd = pair[1];
            count++;
        }
    }

    return count;
}

Python solution

matched/original

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

Go solution

matched/original

import "sort"

func findLongestChain(pairs [][]int) int {
    sort.Slice(pairs, func(i, j int) bool {
        return pairs[i][1] < pairs[j][1]
    })
    currentEnd := -int(^uint(0) >> 1) // Equivalent to -Infinity
    count := 0
    for _, pair := range pairs {
        if currentEnd < pair[0] {
            currentEnd = pair[1]
            count++
        }
    }
    return count
}

Explanation

Algorithm

Отсортируйте пары по второму элементу каждой пары (righti).

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

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

😎