classSolution { publicintfindLongestChain(int[][] pairs) { Arrays.sort(pairs, (a,b)->a[0]-b[0]); intn= pairs.length, ans = 1; int[] f = newint[n]; for (inti=0; i < n; i++) { f[i] = 1; for (intj= i - 1; j >= 0 && f[i] == 1; j--) { if (pairs[j][1] < pairs[i][0]) f[i] = f[j] + 1; } ans = Math.max(ans, f[i]); } return ans; } }
C++ 代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
classSolution { public: intfindLongestChain(vector<vector<int>>& pairs){ sort(pairs.begin(), pairs.end()); int n = pairs.size(), ans = 1; vector<int> f(n, 1); for (int i = 0; i < n; i++) { f[i] = 1; for (int j = i - 1; j >= 0 && f[i] == 1; j--) { if (pairs[j][1] < pairs[i][0]) f[i] = f[j] + 1; } ans = max(ans, f[i]); } return ans; } };
Python 代码:
1 2 3 4 5 6 7 8 9 10 11 12 13
classSolution: deffindLongestChain(self, pairs: List[List[int]]) -> int: pairs.sort() n, ans = len(pairs), 1 f = [1] * n for i inrange(n): j = i - 1 while j >= 0and f[i] == 1: if pairs[j][1] < pairs[i][0]: f[i] = f[j] + 1 j -= 1 ans = max(ans, f[i]) return ans
TypeScript 代码:
1 2 3 4 5 6 7 8 9 10 11 12 13
functionfindLongestChain(pairs: number[][]): number { pairs.sort((a, b) => a[0] - b[0]); let n = pairs.length, ans = 1; constf: number[] = newArray(n).fill(1); for (let i = 0; i < n; i++) { f[i] = 1; for (let j = i - 1; j >= 0 && f[i] == 1; j--) { if (pairs[j][1] < pairs[i][0]) f[i] = f[j] + 1; } ans = Math.max(ans, f[i]); } return ans; };
classSolution { publicintfindLongestChain(int[][] pairs) { Arrays.sort(pairs, (a,b)->a[0]-b[0]); intn= pairs.length, ans = 1; int[] g = newint[n + 10]; Arrays.fill(g, 0x3f3f3f3f); for (inti=0; i < n; i++) { intl=1, r = i + 1; while (l < r) { intmid= l + r >> 1; if (g[mid] >= pairs[i][0]) r = mid; else l = mid + 1; } g[r] = Math.min(g[r], pairs[i][1]); ans = Math.max(ans, r); } return ans; } }
C++ 代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
classSolution { public: intfindLongestChain(vector<vector<int>>& pairs){ sort(pairs.begin(), pairs.end()); int n = pairs.size(), ans = 1; vector<int> g(n + 10, 0x3f3f3f3f); for (int i = 0; i < n; i++) { int l = 1, r = i + 1; while (l < r) { int mid = l + r >> 1; if (g[mid] >= pairs[i][0]) r = mid; else l = mid + 1; } g[r] = min(g[r], pairs[i][1]); ans = max(ans, r); } return ans; } };
Python 代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
classSolution: deffindLongestChain(self, pairs: List[List[int]]) -> int: pairs.sort() n, ans = len(pairs), 1 g = [0x3f3f3f3f] * (n + 10) for i inrange(n): l, r = 1, i + 1 while l < r: mid = l + r >> 1 if g[mid] >= pairs[i][0]: r = mid else: l = mid + 1 g[r] = min(g[r], pairs[i][1]) ans = max(ans, r) return ans
TypeScript 代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
functionfindLongestChain(pairs: number[][]): number { pairs.sort((a, b) => a[0] - b[0]); let n = pairs.length, ans = 1; constg: number[] = newArray(n + 10).fill(0x3f3f3f3f); for (let i = 0; i < n; i++) { let l = 1, r = i + 1; while (l < r) { const mid = l + r >> 1; if (g[mid] >= pairs[i][0]) r = mid; else l = mid + 1; } g[r] = Math.min(g[r], pairs[i][1]); ans = Math.max(ans, r); } return ans; };