0646. Maximum Length of Pair Chain

题目信息

题号:

0646

难度:

Medium

主题:

数对、严格衔接、可重排选择、最长链

原题:

LeetCode 0646

重点:

每个数对满足 left<right、前一对的 right 必须严格小于后一对的 left、输入数对可重新排序、每个数对最多使用一次

题目重述

给定数对数组 pairs,其中每个数对 [left_i, right_i] 都满足 left_i < right_i。若数对 [a, b] 后面接 [c, d],必须满足 b < c。

可以从输入中选择部分数对并任意调整它们的顺序,使其形成一条满足上述严格条件的链。返回能够形成的最长链长度。pairs.length 位于 [1, 1000],端点值位于 [-1000, 1000];同一个输入数对最多使用一次。

自建示例

能够形成三段链:

输入:pairs = [[-3,-1],[0,2],[3,4],[1,5]]
输出:3
解释:[-3,-1]、[0,2]、[3,4] 依次满足 -1<0 和 2<3,构成长度为 3 的链。

端点相等不能衔接:

输入:pairs = [[1,2],[2,3]]
输出:1
解释:第一对的右端点等于第二对的左端点,但题目要求严格小于,因此两对不能组成同一条链。