Solution by passwordusername


  • 1
    P

    Approach #1 Brute Force [Accepted]

    Intuition

    Do as directed in question

    Algorithm

    Hint: the number of ordered Numbers entered by the topic is strictly less than the second number
    This problem is just based on the second number from the small to the big order, and then you start from the bottom table 0, and you go through the pairs,

    Step 1: order the array pairs[][] according to the number of ordered pairs
    Step 2: the variable i iterates from 0 to pairs.length-1,
    Store the second number of the current ordered pairs in the temporary variable temp
    Step 3: add the variable result to 1
    Step 4: if the variable i is less than pairs.length and the number of the first number of ordered pairs is less than the current second number temp,
    add the variable i to 1.Otherwise return step 2
    Step 5: variable result is answer

    Java

    class Solution {
        public int findLongestChain(int[][]pairs) {
            int len=pairs.length;
            int i=0;
            int result=0;
    
            Arrays.sort(pairs,(a,b)->(a[1]-b[1]));
         
            while(i<len)
            {
                int temp=pairs[i][1];
                result=result+1;
                while(i<len&&pairs[i][0]<=temp) 
                    i++;
            }
            return result;
        }
    }
    

    Complexity Analysis

    Time complexity :O(n)

    Space complexity :O(1) space required


  • 0
    N

    Hey the solution looks good, just that the time complexity will be O(nlogn) as you have sorting even though the while loop takes only O(n) to find the solution


Log in to reply
 

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