-
Notifications
You must be signed in to change notification settings - Fork 1
/
chain.go
61 lines (56 loc) · 1.04 KB
/
chain.go
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
package chain
import "sort"
func FindLongestChain(pairs [][]int) int {
l := len(pairs)
if l == 0 {
return 0
}
sort.Slice(pairs, func(i, j int) bool {
return pairs[i][0] < pairs[j][0]
})
// curMax, maxSofar := 1, 1
// head, tail := 0, 0 // index of the smallest pair
// for i := 1; i < len(pairs); i++ {
// if pairs[i][0] > pairs[tail][1] {
// curMax++
// tail = i
// } else {
// if head == tail && pairs[i][1] < pairs[head][1] {
// head = i
// tail = i
// curMax = 1
// }
// }
// if curMax > maxSofar {
// maxSofar = curMax
// }
// }
// return maxSofar
dp := make([]int, l)
for i := 0; i < l; i++ {
dp[i] = 1
}
for i := 1; i < l; i++ {
for j := 0; j < i; j++ {
if pairs[i][0] > pairs[j][1] && dp[i] < dp[j]+1 {
dp[i] = dp[j] + 1
}
}
}
ret := 0
for i := 0; i < l; i++ {
if ret < dp[i] {
ret = dp[i]
}
}
return ret
// ret := 0
// for i := 0; i < l; i++ {
// ret++
// curEnd := pairs[i][1]
// for i+1 < l && pairs[i+1][0] <= curEnd {
// i++
// }
// }
// return ret
}