0646. Maximum Length of Pair Chain¶
题目信息¶
- 题号:
0646
- 难度:
Medium
- 主题:
数对、严格衔接、可重排选择、最长链
- 原题:
- 重点:
每个数对满足 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
解释:第一对的右端点等于第二对的左端点,但题目要求严格小于,因此两对不能组成同一条链。