[LeetCode] 646. Maximum Length of Pair Chain

轉自LeetCode

You are given an array of n pairs pairs where pairs[i] = [lefti, righti] and lefti < righti.

A pair p2 = [c, d] follows a pair p1 = [a, b] if b < c. A chain of pairs can be formed in this fashion.

Return the length longest chain which can be formed.

You do not need to use up all the given intervals. You can select pairs in any order.

 

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].

 

Constraints:

• n == pairs.length
• 1 <= n <= 1000
• -1000 <= lefti < righti <= 1000

Solution

這題和 300. Longest Increasing Subsequence 不同在於

pair 在原本 list 裡面的順序沒有關係，最後的答案只是要找最長的 chain

所以這邊的想法是，先對結束時間做排序，然後歷遍檢查有沒有重疊

kotlin

	class Solution {
	fun findLongestChain(pairs: Array<IntArray>): Int {
	pairs.sortBy { it[1] }
	var end = Int.MIN_VALUE
	var ans = 0
	for(p in pairs) {
	if (p[0] > end) {
	++ans
	end = p[1]
	}
	}
	return ans
	}
	}

view raw maximum_length_of_pair_chain.kt hosted with ❤ by GitHub