4-Liner Python Greedy


  • 21
    def findLongestChain(self, pairs):
        cur, res = float('-inf'), 0
        for p in sorted(pairs, key=lambda x: x[1]):
            if cur < p[0]: cur, res = p[1], res + 1
        return res

  • 0
    F

    My solution followed the same idea after got "time limit exceeded" from my initial DP solution, but yours is obviously much clearer and cleaner. Admire!
    lol and found a benefit of using a bit slower language - always force you to find a better solution. If I were using C++ etc maybe the DP solution would pass with no problem and I'll satisfy with that while miss a smarter solution like this!


  • 0

    Thanks a lot @TianQ. Such a smart and elegant solution. It is easy to think about sorting the list firstly. However, it is not so easy to find such an elegant solution. Meanwhile when should we sort from end when should we sort from the start, it is a critical thing we have to figure out. Fortunately, we only have 3 cases for both sorting by start or sorting by end and they are summarized as bellow:

          
    #1) sort by end:  after sorting we know: s1<e1<e2   and s2<e2
    #(in order to make it be easier, we do not consider about "="). 
    #Then s2 has three possible positions. I am giving those three possibilities by "@". :     @s1@e1@e2 
    #Then we have 3 cases.
           #case 1: s2<s1<e1  @<e2 (replace the first "@"by s2 and remove the rest "@")   
                             #s1****e1
             #s2*****************************e2
    
    
            #case 2:s1<s2<e1 <e2 
             #s1*****************e1
                          #s2*******************e2
            
    
           #case 3:s1<e1< s2 <e2 
            #s1************e1
                                         #s2**************e2
           
    #2) sort by start(similar as sort by end):   s1@s2@e2@
            #case1:    s1 <e1 <s2< e2
             #s1******e1
                                         #s2************e2
    
    
            #case2:    s1<s2<e1<e2
             #s1***************e1
                         #s2**********************e2
    
    
            #case3:s1<s2<e2<e1
              #s1************************************e1
                              #s2********e2
    

    From the summary, we can see: for the 3cases of sorting by start and sorting by end only one case is different, the rest two cases are the same. The different one is case1 of sorting by end and case 3 of sorting by start. By knowing this, it might be helpful to figure out whether we should sort by start or sort by end. After we figure all those out, it might be easier to help us understand the solution provided by TianQ, also it might be helpful for us to resolve the similar problems in the future. Hope it is helps. Thanks.


  • 0
    This post is deleted!

Log in to reply
 

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