这道题本质上是一个interval融合问题。一般我们解决interval问题都是按左边界排序,但是这一道题用右边界排序会更简单。用右边界排序的好处是当第i个和第i+1个interval有重叠的时候,可以果断放弃第i+1个,而不会担心是否错过最优解,因为能和第i+1个融合的interval也必然能和第i个融合。

var findLongestChain = function(pairs) {
    const len = pairs.length;
    if (len <= 1) {
        return len;
    }
    pairs.sort((a, b) => a[1] - b[1]);
    let res = 1;
    let curr = pairs[0];
    let i = 1;
    while (i < len) {
        const next = pairs[i];
        if (curr[1] < next[0]) {
            res++;
            curr = [Math.min(curr[0], next[0]), next[1]];
        }
        i++;
    }
    return res;
};

results matching ""

    No results matching ""