Greed is good, greed is right, greed works!

  • 0

    Enjoy! Greed is Good speech

    def findLongestChain(self, pairs):
        # sort by the second number
        sorted_pairs = sorted(pairs, key=lambda k: k[1])
        # ends_with represents the last seen 'second number'
        i, count, ends_with = 0, 0, float('-infinity')
        while i < len(sorted_pairs):
            pair = sorted_pairs[i]
            start, end = pair
            # search for an interval that starts after the last seen 'second number'
            if ends_with < start:
                ends_with = end
                count += 1
            i += 1
        return count

Log in to reply

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