O(nlogn) Python solution, binary search, easy to understand

  • 1
    def findLongestChain(self, pairs):
        :type pairs: List[List[int]]
        :rtype: int
        # sort by x for pairs (x1, y1), (x2, y2), (x3, y3)...
        # min_end_y[i] is the ending tuple minimum y of length=i chain
        min_end_y = [float('inf')] * len(pairs)
        for x, y in pairs:
            # since (a, b) can chain (c, d) iff b < c, use bisect_left
            i = bisect.bisect_left(min_end_y, x)
            # greedy method, for the same length chain, the smaller y the better
            min_end_y[i] = min(min_end_y[i], y)  
        return bisect.bisect_left(min_end_y, float('inf'))

    See also https://discuss.leetcode.com/topic/28814/another-o-n-log-n-python

Log in to reply

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