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