→ a9486l: 大師 08/26 21:26
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：
-----------------------------------------
class Solution {
public int findLongestChain(int[][] pairs) {
Arrays.sort(pairs, Comparator.comparingInt(a -> a[1]));
int len = 1;
int curr = pairs[0][1];
for (int i = 1; i < pairs.length; i++) {
if (pairs[i][0] > curr) {
curr = pairs[i][1];
len++;
}
}
return len;
}
}
-----------------------------------------
--
https://i.imgur.com/DANRJFR.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1693056253.A.36E.html