Description
給定
n個數對pairs，其中pairs[i] = [left_i, right_i]且left_i < right_i。如果b < c，則可以將[a, b]和[c, d]串成鏈。回傳最長數對鏈的長度。
Example:
Input: pairs = [[1,2],[2,3],[3,4]] Output: 2 (例如 [1,2] -> [3,4])
Intuition#
按右端點排序，貪心選結束最早的數對 — 與「活動選擇問題」相同。
- 經典的區間調度問題（Activity Selection）
- 按右端點排序後，貪心選不重疊的數對
- 每次選右端點最小的，留給後面更多空間
Approaches#
1: DP#
- 概念: 按左端點排序，
dp[i]表示以第i個數對結尾的最長鏈。對每個數對向前找能接上的。 - 時間複雜度:
O(n^2) - 空間複雜度:
O(n)
class Solution {
fun findLongestChain(pairs: Array<IntArray>): Int {
pairs.sortBy { it[0] }
val n = pairs.size
val dp = IntArray(n) { 1 }
for (i in 1 until n) {
for (j in 0 until i) {
if (pairs[j][1] < pairs[i][0]) {
dp[i] = maxOf(dp[i], dp[j] + 1)
}
}
}
return dp.max()
}
}⭐2: 貪心（按右端點排序）#
- 概念: 按右端點排序，貪心選擇：若當前數對的左端點大於上一個選的右端點，就選它。
- 時間複雜度:
O(n log n) - 空間複雜度:
O(1)
class Solution {
fun findLongestChain(pairs: Array<IntArray>): Int {
pairs.sortBy { it[1] }
var count = 1
var end = pairs[0][1]
for (i in 1 until pairs.size) {
if (pairs[i][0] > end) {
count++
end = pairs[i][1]
}
}
return count
}
}🔑 Takeaways#
- Pattern: 區間調度（Activity Selection）— 按結束時間排序，貪心選不重疊的
- 關鍵技巧: 注意是嚴格小於（
b < c）而非小於等於；此問題等價於 LIS 但貪心更快