dp[k] = the lowest right-coordinate of the chain of length k.
Now, let's process elements
(x, y) of
A in ascending order of right-coordinate.
The best way to explain the following code is a worked example on [[1,2],[2,3],[3,4]].
- After [1, 2], dp = [-inf, 2]
- After [2, 3], dp = [-inf, 2] : we cannot extend [2, 3] onto [1, 2], and the length-1 chain ending in 2 dominates the chain [[2,3]] ending in 3.
- After [3, 4], dp = [-inf, 2, 4] : we can extend the chain ending in 2 to be a chain one larger ending in 4.
This problem is similar to https://leetcode.com/problems/longest-increasing-subsequence/#/description , so if you are having trouble, I recommend you review the discussion page of that problem.
def findLongestChain(self, A): dp = [float('-inf')] for x, y in sorted(A, key = lambda z: z): ix = bisect.bisect_left(dp, x) if ix == len(dp): dp.append(y) elif y < dp[ix]: dp[ix] = y return len(dp) - 1
Great solution. Thanks for sharing.
From code inspection and testing, we can see that this check would never be true. Hence, we can ignore this code check as it never gets executed.
elif y < dp[ix]:
dp[ix] = y
This is because, we are going through list sorted by y.
And we are only inserting y to dp.
Hence, in each iteration, y would be greater than any element in dp.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.