26. Maximum Length of Pair Chain

The problem can be found at the following link: Question Link

My Approach

The greedy approch to solve this questiojn is , we can sort the given vector according to their 2nd element . Then we can check if the end value of the first element is less then to start value of the second element . If it is true then we increment our counter and change our current index acoording to end value .

Algorithm

1. Sort the pairs vector in ascending order based on their ending points using the compare function. This step ensures that pairs with smaller ending points come first in the sorted vector.

2. Initialize a variable ans to 1. This variable will keep track of the length of the longest chain.

3. Initialize a variable end to the ending point of the first pair in the sorted pairs vector.

4. Iterate through the sorted pairs vector starting from the second pair (index 1).

5. For each pair at index i, get its starting point si and ending point ei.

6. Check if the starting point si of the current pair is greater than the current end. If it is, this means that you can add this pair to the chain because it doesn't overlap with the previous pair.

7. If si is greater than end, increment the ans variable by 1 to extend the chain length, and update the end variable to be ei (the ending point of the current pair).

8. Continue iterating through the sorted pairs, repeating steps 6-8, until you've processed all pairs.

Time and Auxiliary Space Complexity

• Time Complexity: O(nlogn)

• Auxiliary Space Complexity: O(1)

Code (C++)

class Solution {
public:
    
	// sorting by minimum end
    static bool compare(vector<int> &a, vector<int> &b){
        if(a[1]==b[1]) return a[0]<b[0];
        return a[1]<b[1];
    }
    
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(),pairs.end(),compare);
        
        int ans =1;
        int end=pairs[0][1];
        for(int i=1;i<pairs.size();i++){
            int si=pairs[i][0], ei=pairs[i][1];
        
            if(si>end){
                ans++;
                end=max(end ,ei);
            }
        }
        return ans;
    }
};

Contribution and Support

For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.

If you find this solution helpful, consider supporting us by giving a ⭐ star to the rishabhv12/Daily-Leetcode-Solution repository.