最长数对链 图解题解

最长数对链这道题到底在接什么

给一个数对数组 pairs，每个数对是 [left, right] 且 left 小于 right。规则是：只要前一个数对的 right 严格小于后一个的 left，前一个就能接到后一个前面。要挑出尽量多的数对接成一条链，返回这条链最长能有多长。数对可以跳着挑、不必按原顺序，比如 pairs=[[1,2],[7,8],[4,5]]，[1,2] 接 [4,5] 再接 [7,8]，链长 3。

为什么把所有接法都列一遍会爆

最直接的想法是把所有能接成的链都摆出来，挑最长的。可每个数对选或不选、还要考虑接的先后，组合随数对个数指数级膨胀，数对一多就列不完。不去枚举整条链，改成从左到右扫一遍，边扫边用贪心（每一步只做当下最划算的选择、定了不反悔）决定每个数对接不接。

为什么按右端点排序而不是左端点

先把所有数对按右端点从小到大排好，再从左往右扫。为什么盯右端点？一条链还能接多长，卡在链尾的右端点上——链尾右端点越小，后面数对的左端点越容易越过它，留给后面的空间就越大。所以每次都优先接右端点小的数对，让链尾停得尽量靠前。若改按左端点排，可能先接了一个左端点小、右端点却很大的数对，把后面一大片空间堵死，反而漏掉更优的接法。

扫描时凭一个 end 门槛怎么决定接不接

排好序后用一个变量 end 记住当前链尾的右端点，初值设成一个极小的数，链长 ans 从 0 起。挨个看每个数对：它的左端点只要严格大于 end，就说明能接到链尾后面，把 ans 加一、并把 end 换成这个数对的右端点，门槛随之抬高；左端点没超过 end 就跳过它。这里必须是严格大于，题目要求前一个 right 严格小于后一个 left，两端相等算重叠、接不上。跳过的数对也不亏：它的右端点不比当前 end 小，留着它只会让链尾更靠后、更挤，丢掉不影响后面。

拿题面的三个数对亲手接一遍

拿题面的 pairs=[[1,2],[7,8],[4,5]] 走一遍。先按右端点排序，三个右端点分别是 2、8、5，排完是 [1,2]、[4,5]、[7,8]。end 起手是极小值、ans=0。第一个 [1,2]，左端点 1 远大于 end，接上，ans 变 1，end 更新成 2。第二个 [4,5]，左端点 4 严格大于 2，接上，ans 变 2，end 更新成 5。第三个 [7,8]，左端点 7 严格大于 5，接上，ans 变 3，end 更新成 8。三个都接进来了，答案 3，和题面输出对上。

复杂度是多少，end 初值和相等两个坑

开销集中在排序，O(n log n)（大 O 记号描述规模变大时操作数怎么涨），n 是数对个数；排完只扫一遍是 O(n)，加起来仍由排序主导。只用了 end、ans 两个变量，空间 O(1)。三个边界最容易踩坑：一是 end 初值要设成足够小的负数，数对可能带负数，设成 0 会让第一个数对接不进来；二是判断写成左端点大于等于 end 就错了，相等的两端接上会重叠，必须严格大于；三是只有一个数对时直接返回 1，它自己就算一条链。

Python

from typing import List
class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        pairs.sort(key=lambda x: x[1])
        ans = 0
        end = -10**18
        for a, b in pairs:
            if a > end:
                ans += 1
                end = b
        return ans

C++

#include <algorithm>
#include <climits>
#include <vector>
using namespace std;
class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(), pairs.end(), [](auto& a, auto& b){ return a[1] < b[1]; });
        int ans = 0, end = INT_MIN;
        for (auto &p : pairs) if (p[0] > end) { ans++; end = p[1]; }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, Comparator.comparingInt(a -> a[1]));
        int ans = 0, end = Integer.MIN_VALUE;
        for (int[] p : pairs) if (p[0] > end) { ans++; end = p[1]; }
        return ans;
    }
}