| comments | difficulty | edit_url | tags | ||||
|---|---|---|---|---|---|---|---|
true |
中等 |
|
给你一个由 n 个数对组成的数对数组 pairs ，其中 pairs[i] = [lefti, righti] 且 lefti < righti 。
现在，我们定义一种 跟随 关系，当且仅当 b < c 时，数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面。我们用这种形式来构造 数对链 。
找出并返回能够形成的 最长数对链的长度 。
你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
示例 1：
输入：pairs = [[1,2], [2,3], [3,4]] 输出：2 解释：最长的数对链是 [1,2] -> [3,4] 。
示例 2：
输入：pairs = [[1,2],[7,8],[4,5]] 输出：3 解释：最长的数对链是 [1,2] -> [4,5] -> [7,8] 。
提示：
n == pairs.length1 <= n <= 1000-1000 <= lefti < righti <= 1000
先将 pairs 按照第一个数字升序排列，然后转换为最长上升子序列问题。
朴素做法，时间复杂度
class Solution:
def findLongestChain(self, pairs: List[List[int]]) -> int:
pairs.sort()
dp = [1] * len(pairs)
for i, (c, _) in enumerate(pairs):
for j, (_, b) in enumerate(pairs[:i]):
if b < c:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)class Solution {
public int findLongestChain(int[][] pairs) {
Arrays.sort(pairs, Comparator.comparingInt(a -> a[0]));
int n = pairs.length;
int[] dp = new int[n];
int ans = 0;
for (int i = 0; i < n; ++i) {
dp[i] = 1;
int c = pairs[i][0];
for (int j = 0; j < i; ++j) {
int b = pairs[j][1];
if (b < c) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
ans = Math.max(ans, dp[i]);
}
return ans;
}
}class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end());
int n = pairs.size();
vector<int> dp(n, 1);
for (int i = 0; i < n; ++i) {
int c = pairs[i][0];
for (int j = 0; j < i; ++j) {
int b = pairs[j][1];
if (b < c) dp[i] = max(dp[i], dp[j] + 1);
}
}
return *max_element(dp.begin(), dp.end());
}
};func findLongestChain(pairs [][]int) int {
sort.Slice(pairs, func(i, j int) bool {
return pairs[i][0] < pairs[j][0]
})
n := len(pairs)
dp := make([]int, n)
ans := 0
for i := range pairs {
dp[i] = 1
c := pairs[i][0]
for j := range pairs[:i] {
b := pairs[j][1]
if b < c {
dp[i] = max(dp[i], dp[j]+1)
}
}
ans = max(ans, dp[i])
}
return ans
}function findLongestChain(pairs: number[][]): number {
pairs.sort((a, b) => a[0] - b[0]);
const n = pairs.length;
const dp = new Array(n).fill(1);
for (let i = 0; i < n; i++) {
for (let j = 0; j < i; j++) {
if (pairs[i][0] > pairs[j][1]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return dp[n - 1];
}impl Solution {
pub fn find_longest_chain(mut pairs: Vec<Vec<i32>>) -> i32 {
pairs.sort_by(|a, b| a[0].cmp(&b[0]));
let n = pairs.len();
let mut dp = vec![1; n];
for i in 0..n {
for j in 0..i {
if pairs[i][0] > pairs[j][1] {
dp[i] = dp[i].max(dp[j] + 1);
}
}
}
dp[n - 1]
}
}在所有可作为下一个数对的集合中，选择第二个数最小的数对添加到数对链。因此可以按照第二个数升序排列的顺序遍历所有数对，如果当前数能加入链，则加入。
时间复杂度
class Solution:
def findLongestChain(self, pairs: List[List[int]]) -> int:
ans, cur = 0, -inf
for a, b in sorted(pairs, key=lambda x: x[1]):
if cur < a:
cur = b
ans += 1
return ansclass Solution {
public int findLongestChain(int[][] pairs) {
Arrays.sort(pairs, Comparator.comparingInt(a -> a[1]));
int ans = 0;
int cur = Integer.MIN_VALUE;
for (int[] p : pairs) {
if (cur < p[0]) {
cur = p[1];
++ans;
}
}
return ans;
}
}class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end(), [](vector<int>& a, vector<int> b) {
return a[1] < b[1];
});
int ans = 0, cur = INT_MIN;
for (auto& p : pairs) {
if (cur < p[0]) {
cur = p[1];
++ans;
}
}
return ans;
}
};func findLongestChain(pairs [][]int) int {
sort.Slice(pairs, func(i, j int) bool {
return pairs[i][1] < pairs[j][1]
})
ans, cur := 0, math.MinInt32
for _, p := range pairs {
if cur < p[0] {
cur = p[1]
ans++
}
}
return ans
}function findLongestChain(pairs: number[][]): number {
pairs.sort((a, b) => a[1] - b[1]);
let res = 0;
let pre = -Infinity;
for (const [a, b] of pairs) {
if (pre < a) {
pre = b;
res++;
}
}
return res;
}impl Solution {
pub fn find_longest_chain(mut pairs: Vec<Vec<i32>>) -> i32 {
pairs.sort_by(|a, b| a[1].cmp(&b[1]));
let mut res = 0;
let mut pre = i32::MIN;
for pair in pairs.iter() {
let a = pair[0];
let b = pair[1];
if pre < a {
pre = b;
res += 1;
}
}
res
}
}