2023-12-06：用go语言，给你一个由 n 个数对组成的数对数组 pairs， 其中 pairs[i] = [lefti,

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：

灵捷3.5

大体步骤如下：

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] 

})

ends := make([]int, n)

size := 0

for _, pair := range pairs {

l, r := 0, size-1

m, find := 0, -1

for l 

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) -> 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 

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![vec![1, 2], vec![2, 3], vec![3, 4]];

let result = find_longest_chain(pairs);

println!("{}", result);

}

在这里插入图片描述c++完整代码如下：

#include 

#include 

#include 

int findLongestChain(std::vector& pairs) {

int n = pairs.size();

std::sort(pairs.begin(), pairs.end(), [](const std::vector& a, const std::vector& b) {

return a[0] 

});

std::vector 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 

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 pairs{ {1,2}, {2,3}, {3,4} };

int result = findLongestChain(pairs);

std::cout 

return 0;

}

在这里插入图片描述c完整代码如下：

#include 

#include 

int findLongestChain(int** pairs, int pairsSize, int* pairsColSize) {

// 根据第一列排序

for (int i = 0; i 

for (int j = 0; 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 

int l = 0;

int r = size - 1;

int m = 0;

int find = -1;

while (l 

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] 

}

}

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;

}

在这里插入图片描述