646. Maximum Length of Pair Chain

LeetCode medium original: C# #array #csharp #dynamic-programming #graph #greedy #intervals #leetcode #medium #search #sort #two-pointers

Il testo del problema è tradotto dal russo per la lingua selezionata. Il codice resta invariato.

LeetCode Static

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

Esempio:

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

Output: [2,3]

C# soluzione

abbinato/originale

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++ soluzione

bozza automatica, rivedere prima dell'invio

#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 soluzione

abbinato/originale

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 soluzione

abbinato/originale

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 soluzione

abbinato/originale

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 soluzione

abbinato/originale

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
}

Algorithm

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

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

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

😎

Vacancies for this task

offerte attive with overlapping task tags are mostrati.

Tutte le offerte

Non ci sono ancora offerte attive.