-
-
Notifications
You must be signed in to change notification settings - Fork 299
/
646.java
62 lines (59 loc) · 1.83 KB
/
646.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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
__________________________________________________________________________________________________
sample 3 ms submission
class Solution {
public int findLongestChain(int[][] pairs) {
if (pairs == null)
return 0;
int len = pairs.length;
if (len < 2)
return len;
qsort(pairs, 0, len - 1);
int sum = 1;
int end = pairs[0][1];
for (int i = 1; i < len; i++) {
if (pairs[i][0] > end) {
sum++;
end = pairs[i][1];
}
}
return sum;
}
private void qsort(int[][] pairs, int begin, int end) {
if (begin >= end)
return;
int key = pairs[begin][1];
int[] keyPair = pairs[begin];
int i = begin, j = end;
while(i < j) {
while(i < j && key <= pairs[j][1])
--j;
pairs[i] = pairs[j];
while(i < j && key >= pairs[i][1])
++i;
pairs[j] = pairs[i];
}
pairs[i] = keyPair;
qsort(pairs, begin, i - 1);
qsort(pairs, i + 1, end);
}
}
__________________________________________________________________________________________________
sample 37340 kb submission
class Solution {
public int findLongestChain(int[][] pairs) {
Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
int N = pairs.length;
int[] dp = new int[N];
Arrays.fill(dp, 1);
for (int j = 1; j < N; ++j) {
for (int i = 0; i < j; ++i) {
if (pairs[i][1] < pairs[j][0])
dp[j] = Math.max(dp[j], dp[i] + 1);
}
}
int ans = 0;
for (int x: dp) if (x > ans) ans = x;
return ans;
}
}
__________________________________________________________________________________________________