646 最长数对链（求解最多不相交区间的个数-贪心）

超、凢脫俗 2022-08-29 05:56 12阅读 0赞

**1. 问题描述：**

给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

**示例：**

输入：\[\[1,2\], \[2,3\], \[3,4\]\]  
输出：2  
解释：最长的数对链是 \[1,2\] -> \[3,4\]

**提示：**

给出数对的个数在 \[1, 1000\] 范围内。  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/maximum-length-of-pair-chain

**2. 思路分析：**

分析题目可以知道本质上求解的是最多不相交区间的个数，求解最多不相交区间的个数问题是经典的**贪心问题**。首先需要对区间的右端点进行由小到大排序，然后从前往后遍历数组，第一个区间是一定要选的，贪心的策略是能够选当前区间的前提下就选择当前的区间，这样一定可以选择最多不相交区间的个数。为什么贪心的策略是正确的呢？这里可以简单证明一下，我们的目标是证明贪心解等于最优解，证明一个相等的问题可以证明两个方向，例如要证明A = B，我们可以证明A >= B和A <= B，那么就可以得到A = B，所以我们需要证明贪心解 >= 最优解并且贪心解 <= 最优解即可，首先最优解一定是区间个数最多的，所以最优解一定大于等于贪心解，那么我们只需证明贪心解 >= 最优解即可，我们可以从前往后遍历贪心解，找到第一个与最优解区间不相等的位置，因为贪心解的右端点是从小到大排序的，所以当前不相等的区间是所有区间中可以选的最靠左的区间我们可以交换一下贪心解与最优解当前不相等的区间可以发现交换之后的区间也是满足题目要求的，并且交换之后得到的区间的右端点更靠左了，所以我们可以对所有贪心解与最优解中不相等的区间进行交换那么得到的不相交的区间个数一定是大于等于最优解的，所以两个方向的证明完毕，那么贪心解就一定等于最优解。

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        def findLongestChain(self, pairs: List[List[int]]) -> int:
            pairs.sort(key=lambda x: x[1])
            # 第一个区间是必选的
            last = pairs[0][1]
            res = 1
            for p in pairs:
                if p[0] > last:
                    # 更新当前区间右端点
                    last = p[1]
                    res += 1
            return res