2023-12-06：用go语言，给你一个由 n 个数对组成的数对数组 pairs，
其中 pairs[i] = [lefti, righti] 且 lefti < righti 。
现在，我们定义一种 跟随 关系，当且仅当 b < c 时，
数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面，
我们用这种形式来构造 数对链。
找出并返回能够形成的 最长数对链的长度。
你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
输入：pairs = [[1,2], [2,3], [3,4]]。
输出：2。
答案2023-12-06：
大体步骤如下：
1.首先对数对数组 pairs 按照左边界进行排序，确保数对按照左边界的升序排列。
2.创建一个大小为 n 的整型数组 ends，用于存储当前数对链中每个数对的右边界值。
3.初始化变量 size 为 0，表示当前数对链的长度。
4.遍历排序后的数对数组 pairs：
-
对于每个数对 pair，使用二分搜索找到 ends 数组中第一个大于等于 pair[0] 的索引 find。
-
如果找不到这样的索引，则将 pair[1] 添加到 ends 数组末尾，并将 size 加一。
-
如果找到了索引 find，则更新 ends[find] 的值为 min(ends[find], pair[1])。这是因为我们要构建最长数对链，所以应该选择右边界更小的数对。
5.返回变量 size 即为能够形成的最长数对链长度。
总的时间复杂度：在排序和遍历过程中，都需要 O(n log n) 的时间复杂度（排序花费 O(n log n)，遍历花费 O(n)）。而二分搜索操作也需要 O(log n) 的时间复杂度。所以总体上是 O(n log n)。
总的额外空间复杂度：除了存储输入数据之外，我们额外使用了一个大小为 n 的数组 ends 来存储数对链的右边界。因此，额外空间复杂度是 O(n)。
go完整代码如下：
package main
import (
"fmt"
"sort"
)
func findLongestChain(pairs [][]int) int {
n := len(pairs)
sort.Slice(pairs, func(i, j int) bool {
return pairs[i][0] < pairs[j][0]
})
ends := make([]int, n)
size := 0
for _, pair := range pairs {
l, r := 0, size-1
m, find := 0, -1
for l <= r {
m = (l + r) / 2
if ends[m] >= pair[0] {
find = m
r = m - 1
} else {
l = m + 1
}
}
if find == -1 {
ends[size] = pair[1]
size++
} else {
if ends[find] > pair[1] {
ends[find] = pair[1]
}
}
}
return size
}
func main() {
pairs := [][]int{{1,2}, {2,3}, {3,4}}
result := findLongestChain(pairs)
fmt.Println(result)
}
rust完整代码如下：
fn find_longest_chain(pairs: Vec<Vec<i32>>) -> i32 {
let mut pairs = pairs;
pairs.sort_by(|a, b| a[0].cmp(&b[0]));
let n = pairs.len() as i32;
let mut ends = vec![0; n as usize];
let mut size: i32 = 0;
for pair in &pairs {
let (mut l, mut r) = (0, size - 1);
let (mut m, mut find) = (0, -1);
while l <= r {
m = (l + r) / 2;
if ends[m as usize] >= pair[0] {
find = m;
r = m - 1;
} else {
l = m + 1;
}
}
if find == -1 {
ends[size as usize] = pair[1];
size += 1;
} else {
ends[find as usize] = ends[find as usize].min(pair[1]);
}
}
size as i32
}
fn main() {
let pairs: Vec<Vec<i32>> = vec![vec![1, 2], vec![2, 3], vec![3, 4]];
let result = find_longest_chain(pairs);
println!("{}", result);
}
c++完整代码如下：
#include <iostream>
#include <vector>
#include <algorithm>
int findLongestChain(std::vector<std::vector<int>>& pairs) {
int n = pairs.size();
std::sort(pairs.begin(), pairs.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
return a[0] < b[0];
});
std::vector<int> ends(n, 0);
int size = 0;
for (const auto& pair : pairs) {
int l = 0;
int r = size - 1;
int m = 0;
int find = -1;
while (l <= r) {
m = (l + r) / 2;
if (ends[m] >= pair[0]) {
find = m;
r = m - 1;
}
else {
l = m + 1;
}
}
if (find == -1) {
ends[size++] = pair[1];
}
else {
ends[find] = std::min(ends[find], pair[1]);
}
}
return size;
}
int main() {
std::vector<std::vector<int>> pairs{ {1,2}, {2,3}, {3,4} };
int result = findLongestChain(pairs);
std::cout << result << std::endl;
return 0;
}
c完整代码如下：
#include <stdio.h>
#include <stdlib.h>
int findLongestChain(int** pairs, int pairsSize, int* pairsColSize) {
// 根据第一列排序
for (int i = 0; i < pairsSize; i++) {
for (int j = 0; j < pairsSize - i - 1; j++) {
if (pairs[j][0] > pairs[j + 1][0]) {
int* temp = pairs[j];
pairs[j] = pairs[j + 1];
pairs[j + 1] = temp;
}
}
}
int* ends = (int*)malloc(sizeof(int) * pairsSize);
int size = 0;
for (int i = 0; i < pairsSize; i++) {
int l = 0;
int r = size - 1;
int m = 0;
int find = -1;
while (l <= r) {
m = (l + r) / 2;
if (ends[m] >= pairs[i][0]) {
find = m;
r = m - 1;
}
else {
l = m + 1;
}
}
if (find == -1) {
ends[size++] = pairs[i][1];
}
else {
ends[find] = ends[find] < pairs[i][1] ? ends[find] : pairs[i][1];
}
}
free(ends);
return size;
}
int main() {
// 输入数据
int pair_1[] = { 1, 2 };
int pair_2[] = { 2, 3 };
int pair_3[] = { 3, 4 };
int* pairs[] = { pair_1, pair_2, pair_3 };
int pairsSize = sizeof(pairs) / sizeof(pairs[0]);
int pairsColSize[] = { 2, 2, 2 };
int result = findLongestChain(pairs, pairsSize, pairsColSize);
printf("%d\n", result);
return 0;
}
