Python, Straightforward with Explanation (N log N)


  • 1

    Let's remember 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[1]):
            ix = bisect.bisect_left(dp, x)
            if ix == len(dp):
                dp.append(y)
            elif y < dp[ix]:
                dp[ix] = y
        return len(dp) - 1
    

  • 2
    S

    @awice

    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.


  • 0
    A

    No need bisect either, greedy algorithm should work


  • 0

    Does this one look better?

    class Solution(object):
        def findLongestChain(self, pairs):
            tails = []
            for start, end in sorted(pairs):
                idx = bisect.bisect_left(tails, start)
                if idx == len(tails):
                    tails.append(end)
                else:
                    tails[idx] = min(tails[idx], end)
            return len(tails)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.