0646-最长数对链

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:23 2023-09-13 16:06:23 Updated    

给你一个由 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.length
  • 1 <= n <= 1000
  • -1000 <= lefti < righti <= 1000

前言

这题和「435. 无重叠区间 」类似，区别就是：

  1. 此题中，数对链中相邻的数对，前者的第二个数字必须小于后者的第一个数字。而在「435. 无重叠区间 」中，相邻的区间，前者的结束时间需小于等于后者的开始时间。
  2. 此题返回最长数对链的长度，而 「435. 无重叠区间 」返回形成无重叠区间，最少需要删除多少区间（即原长度减去最长数对链的长度）。

此题解也按照「435. 无重叠区间的官方题解 」进行编写。

方法一：动态规划

思路

定义 dp}[i] 为以 pairs}[i] 为结尾的最长数对链的长度。计算 dp}[i] 时，可以先找出所有的满足 pairs}[i][0] > \textit{pairs}[j][1] 的 j，并求出最大的 dp}[j]，dp}[i] 的值即可赋为这个最大值加一。这种动态规划的思路要求计算 dp}[i] 时，所有潜在的 dp}[j] 已经计算完成，可以先将 pairs 进行排序来满足这一要求。初始化时，dp 需要全部赋值为 1。

代码

[sol1-Python3]
1
2
3
4
5
6
7
8
9
class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        pairs.sort()
        dp = [1] * len(pairs)
        for i in range(len(pairs)):
            for j in range(i):
                if pairs[i][0] > pairs[j][1]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return dp[-1]
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        int n = pairs.size();
        sort(pairs.begin(), pairs.end());
        vector<int> dp(n, 1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (pairs[i][0] > pairs[j][1]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[n - 1];
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int findLongestChain(int[][] pairs) {
        int n = pairs.length;
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 0; i < n; i++) {
            for (int 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];
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int FindLongestChain(int[][] pairs) {
        int n = pairs.Length;
        Array.Sort(pairs, (a, b) => a[0] - b[0]);
        int[] dp = new int[n];
        Array.Fill(dp, 1);
        for (int i = 0; i < n; i++) {
            for (int 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];
    }
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#define MAX(a, b) ((a) > (b) ? (a) : (b))

static inline int cmp(const void *pa, const void *pb) {
    if ((*(int **)pa)[0] == (*(int **)pb)[0]) {
        return (*(int **)pa)[1] == (*(int **)pb)[1];
    } 
    return (*(int **)pa)[0] - (*(int **)pb)[0];
}

int findLongestChain(int** pairs, int pairsSize, int* pairsColSize){
    qsort(pairs, pairsSize, sizeof(int *), cmp);
    int *dp = (int *)malloc(sizeof(int) * pairsSize);
    for (int i = 0; i < pairsSize; i++) {
        dp[i] = 1;
    }
    for (int i = 0; i < pairsSize; i++) {
        for (int j = 0; j < i; j++) {
            if (pairs[i][0] > pairs[j][1]) {
                dp[i] = MAX(dp[i], dp[j] + 1);
            }
        }
    }
    int ret = dp[pairsSize - 1];
    free(dp);
    return ret;
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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)
    for i, p := range pairs {
        dp[i] = 1
        for j, q := range pairs[:i] {
            if p[0] > q[1] {
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
    }
    return dp[n-1]
}

func max(a, b int) int {
    if b > a {
        return b
    }
    return a
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
var findLongestChain = function(pairs) {
    const n = pairs.length;
    pairs.sort((a, b) => a[0] - b[0]);
    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];
};

复杂度分析

  • 时间复杂度：O(n^2)，其中 n 为 pairs 的长度。排序的时间复杂度为 O(n \log n)，两层 for 循环的时间复杂度为 O(n^2)。

  • 空间复杂度：O(n)，数组 dp 的空间复杂度为 O(n)。

方法二：最长递增子序列

思路

方法一实际上是「300. 最长递增子序列 」的动态规划解法，这个解法可以改造为贪心 + 二分查找的形式。用一个数组 arr 来记录当前最优情况，arr}[i] 就表示长度为 i+1 的数对链的末尾可以取得的最小值，遇到一个新数对时，先用二分查找得到这个数对可以放置的位置，再更新 arr。

代码

[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        pairs.sort()
        arr = []
        for x, y in pairs:
            i = bisect_left(arr, x)
            if i < len(arr):
                arr[i] = min(arr[i], y)
            else:
                arr.append(y)
        return len(arr)
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(), pairs.end());
        vector<int> arr;
        for (auto p : pairs) {
            int x = p[0], y = p[1];
            if (arr.size() == 0 || x > arr.back()) {
                arr.emplace_back(y);
            } else {
                int idx = lower_bound(arr.begin(), arr.end(), x) - arr.begin();
                arr[idx] = min(arr[idx], y);
            }
        }
        return arr.size();
    }
};
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
        List<Integer> arr = new ArrayList<Integer>();
        for (int[] p : pairs) {
            int x = p[0], y = p[1];
            if (arr.isEmpty() || x > arr.get(arr.size() - 1)) {
                arr.add(y);
            } else {
                int idx = binarySearch(arr, x);
                arr.set(idx, Math.min(arr.get(idx), y));
            }
        }
        return arr.size();
    }

    public int binarySearch(List<Integer> arr, int x) {
        int low = 0, high = arr.size() - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (arr.get(mid) >= x) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
}
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
    public int FindLongestChain(int[][] pairs) {
        Array.Sort(pairs, (a, b) => a[0] - b[0]);
        IList<int> arr = new List<int>();
        foreach (int[] p in pairs) {
            int x = p[0], y = p[1];
            if (arr.Count == 0 || x > arr[arr.Count - 1]) {
                arr.Add(y);
            } else {
                int idx = BinarySearch(arr, x);
                arr[idx] = Math.Min(arr[idx], y);
            }
        }
        return arr.Count;
    }

    public int BinarySearch(IList<int> arr, int x) {
        int low = 0, high = arr.Count - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] >= x) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
}
[sol2-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#define MIN(a, b) ((a) < (b) ? (a) : (b))

static inline int cmp(const void *pa, const void *pb) {
    if ((*(int **)pa)[0] == (*(int **)pb)[0]) {
        return (*(int **)pa)[1] == (*(int **)pb)[1];
    } 
    return (*(int **)pa)[0] - (*(int **)pb)[0];
}

int lowerbound(const int *arr, int left, int right, int val) {
    int ret = -1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (arr[mid] >= val) {
            ret = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ret;
}

int findLongestChain(int** pairs, int pairsSize, int* pairsColSize){
    qsort(pairs, pairsSize, sizeof(int *), cmp);
    int *arr = (int *)malloc(sizeof(int) * pairsSize);
    int pos = 0;
    for (int i = 0; i < pairsSize; i++) {
        int x = pairs[i][0], y = pairs[i][1];
        if (pos == 0 || x > arr[pos - 1]) {
            arr[pos++] = y;
        } else {
            int idx = lowerbound(arr, 0, pos - 1, x);
            arr[idx] = MIN(arr[idx], y);
        }
    }
    free(arr);
    return pos;
}
[sol2-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func findLongestChain(pairs [][]int) int {
    sort.Slice(pairs, func(i, j int) bool { return pairs[i][0] < pairs[j][0] })
    arr := []int{}
    for _, p := range pairs {
        i := sort.SearchInts(arr, p[0])
        if i < len(arr) {
            arr[i] = min(arr[i], p[1])
        } else {
            arr = append(arr, p[1])
        }
    }
    return len(arr)
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}
[sol2-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
var findLongestChain = function(pairs) {
    pairs.sort((a, b) => a[0] - b[0]);
    const arr = [];
    for (const p of pairs) {
        let x = p[0], y = p[1];
        if (arr.length === 0 || x > arr[arr.length - 1]) {
            arr.push(y);
        } else {
            const idx = binarySearch(arr, x);
            arr[idx] =  Math.min(arr[idx], y);
        }
    }
    return arr.length;
}

const binarySearch = (arr, x) => {
    let low = 0, high = arr.length - 1;
    while (low < high) {
        const mid = low + Math.floor((high - low) / 2);
        if (arr[mid] >= x) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
};

复杂度分析

  • 时间复杂度：O(n \log n)，其中 n 为 pairs 的长度。排序的时间复杂度为 O(n \log n)，二分查找的时间复杂度为 O(n \log n)，二分的次数为 O(n)。

  • 空间复杂度：O(n)，数组 arr 的长度最多为 O(n)。

方法三：贪心

思路

要挑选最长数对链的第一个数对时，最优的选择是挑选第二个数字最小的，这样能给挑选后续的数对留下更多的空间。挑完第一个数对后，要挑第二个数对时，也是按照相同的思路，是在剩下的数对中，第一个数字满足题意的条件下，挑选第二个数字最小的。按照这样的思路，可以先将输入按照第二个数字排序，然后不停地判断第一个数字是否能满足大于前一个数对的第二个数字即可。

代码

[sol3-Python3]
1
2
3
4
5
6
7
8
class Solution(object):
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        cur, res = -inf, 0
        for x, y in sorted(pairs, key=lambda p: p[1]):
            if cur < x:
                cur = y
                res += 1
        return res
[sol3-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        int curr = INT_MIN, res = 0;
        sort(pairs.begin(), pairs.end(), [](const vector<int> &a, const vector<int> &b) {
            return a[1] < b[1];
        });
        for (auto &p : pairs) {
            if (curr < p[0]) {
                curr = p[1];
                res++;
            }
        }
        return res;
    }
};
[sol3-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int findLongestChain(int[][] pairs) {
        int curr = Integer.MIN_VALUE, res = 0;
        Arrays.sort(pairs, (a, b) -> a[1] - b[1]);
        for (int[] p : pairs) {
            if (curr < p[0]) {
                curr = p[1];
                res++;
            }
        }
        return res;
    }
}
[sol3-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public int FindLongestChain(int[][] pairs) {
        int curr = int.MinValue, res = 0;
        Array.Sort(pairs, (a, b) => a[1] - b[1]);
        foreach (int[] p in pairs) {
            if (curr < p[0]) {
                curr = p[1];
                res++;
            }
        }
        return res;
    }
}
[sol3-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static inline int cmp(const void *pa, const void *pb) {
    return (*(int **)pa)[1] - (*(int **)pb)[1];
}

int findLongestChain(int** pairs, int pairsSize, int* pairsColSize){
    int curr = INT_MIN, res = 0;
    qsort(pairs, pairsSize, sizeof(int *), cmp);
    for (int i = 0; i < pairsSize; i++) {
        if (curr < pairs[i][0]) {
            curr = pairs[i][1];
            res += 1;
        }
    }
    return res;
}
[sol3-Golang]
1
2
3
4
5
6
7
8
9
10
11
func findLongestChain(pairs [][]int) (ans int) {
    sort.Slice(pairs, func(i, j int) bool { return pairs[i][1] < pairs[j][1] })
    cur := math.MinInt32
    for _, p := range pairs {
        if cur < p[0] {
            cur = p[1]
            ans++
        }
    }
    return
}
[sol3-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
var findLongestChain = function(pairs) {
    let curr = -Number.MAX_VALUE, res = 0;
    pairs.sort((a, b) => a[1] - b[1]);
    for (const p of pairs) {
        if (curr < p[0]) {
            curr = p[1];
            res++;
        }
    }
    return res;
}

复杂度分析

  • 时间复杂度：O(n \log n)，其中 n 为 pairs 的长度。排序的时间复杂度为 O(n \log n)。

  • 空间复杂度：O(\log n)，为排序的空间复杂度。

 Comments
On this page
0646-最长数对链