| 79 | """ |
| 80 | |
| 81 | class Solution(object): |
| 82 | def findLongestChain(self, pairs): |
| 83 | """ |
| 84 | :type pairs: List[List[int]] |
| 85 | :rtype: int |
| 86 | """ |
| 87 | if not pairs: |
| 88 | return 0 |
| 89 | # O (nlogn) + O(n) |
| 90 | # x = sorted(pairs, key=lambda x: x[1]) |
| 91 | |
| 92 | # mins = x[0] |
| 93 | |
| 94 | # maxes = 1 |
| 95 | |
| 96 | # for i in x: |
| 97 | # if i[0] > mins[1]: |
| 98 | # maxes += 1 |
| 99 | # mins = i |
| 100 | # return maxes |
| 101 | |
| 102 | # O(n²) |
| 103 | pairs.sort(key=lambda x: x[1]) |
| 104 | dp = [1] |
| 105 | |
| 106 | currentMaxes = 0 |
| 107 | |
| 108 | for i in range(1, len(pairs)): |
| 109 | maxes = max([dp[j]+1 if pairs[i][0] > pairs[j][1] else 1 for j in range(i)]) |
| 110 | dp.append(maxes) |
| 111 | currentMaxes = max(maxes, currentMaxes) |
| 112 | |
| 113 | |
| 114 | return currentMaxes |
| 115 |
nothing calls this directly
no outgoing calls
no test coverage detected