Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2023-08-26 21:24:10
https://leetcode.com/problems/maximum-length-of-pair-chain/description/
646. Maximum Length of Pair Chain
给你一个二维阵列 pairs ,pairs[i] = [left, right] 且 left < right。
一个 chain p1,p2 如果成立,表示满足 p1 = [a, b] p2 = [c, d] 且 b < c。
求出 chain 的最长长度。
Example 1:
Input: pairs = [[1,2],[2,3],[3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4].
Example 2:
Input: pairs = [[1,2],[7,8],[4,5]]
Output: 3
Explanation: The longest chain is [1,2] -> [4,5] -> [7,8].
思路:
1.因为 pair[i] = [left, right] 之中 right 一定大于 left,而如果
right 越小就表示我们可以串起更长的 chain。
2.所以我们可以对 right 做贪婪,依照每个 pair 的 right 去排序,每次
都取满足 p1 = [a, b] p2 = [c, d] 且 b < c 的 pair 加入 chain,这样
串起来的 chain 必定是最长(因为 right 很大的 pair 都被排在最后面)。
Java Code:
作者: a9486l (a9486l)   2023-08-26 21:26:00
大师

Links booklink

Contact Us: admin [ a t ] ucptt.com