Maximum length pair chain

We will solve this problem recursively by dividing it into subproblems. We first need to sort the array according to their first element. But why? as it is given in the question that you can pick any pair in any order so if you pick a pair at index ‘i’ then for the next pair you need to try all pairs from [0, ‘N’ - 1] which are not selected in the current chain that will make our implementation more difficult. So with the help of sorting the array, we ensure that our next pair will always lie after the chosen index ‘i’.

After the sorting, for each pair we have two choices: either we can include this pair in our current chain or do not include this pair in our current chain.

• If we do not include this pair in our current chain then we can simply skip this pair and recur for the next pair present on index ‘i' +1.
• If we include this pair in our current chain then we increment our length by 1 and recur on the next possible pair which satisfies the condition that the next pair should have its first element greater than the second element of the current pair.
• Also, we already sort the array so we know the next possible pair will lie after the current pair i.e, if the index of the current pair is ‘i’ then we will recur in the range ['i' + 1, ‘N’ - 1] for the next possible pair.
• At each step, we will take the maximum length which we can get by the above two choices for the current pair.

We will sort the array according to the first element to define an order of picking pairs in the chain. We will use a ‘DP’ table of size ‘N’ to memoize the results for each index. Definition: dp[i] will store the max length pair chain starting from index ‘i’. 

If the result is already calculated then we simply return it else we will calculate the answer for the current index. 

Transitions: Let our function be solve(i) then for the current pair we have 2 choices:

• We do not include this pair in our chain then, in that case, we simply skip this pair and go to the next state which is solve('i'+1).
• We include this pair in our chain and try all the next possible pair which satisfy the given condition (the next pair should have its first element greater than the second element of the current pair) so the transition will solve('j') where ‘i’+1 <= ‘j’ <= ‘N’ - 1.
• From the above possibilities, we take the one having which will return maximum length.
• Base case: if we reach the end of an array that means there are no pairs available for extending our chain in that case we will return 0.

This problem is a variation of LIS (longest increasing subsequence). We will sort the array according to the first element to define an order of picking pairs in the chain. Now the elements are sorted according to the first elements we need to find the longest increasing subsequence according to their second elements. 

We will use a ‘DP’ table of size ‘N’ to calculate the results for each index. Definition: ‘DP’[i] will store the max length pair chain ending at index ‘i’.

• Base case: Each pair can make a valid chain of length 1 so we initialize each entry in the ‘DP’ table with value 1.
• Transitions: If the current pair is the ending element of the chain then the maximum length of pair chain ending at this pair will be 1 + maximum ‘DP[j]’ where 0<= ‘j’ < ‘i’ and the first element of the current pair is greater than the second element of the pair having index ‘j’.
• The final answer will be the maximum length among all the lengths we found so far in our ‘DP’ table.

This problem can also be solved using the Activity selection greedy approach because it is given in the question that the first element of the pair is always less than the second element of the pair. We sort the pairs according to the second element and then we greedily add the next pair to our chain that offers the most obvious and immediate benefit i.e, the pair having the lowest second element in the remaining pairs.

Proof: Suppose we have two pairs ‘P[i]' and ‘P[j]’ where ‘P[i]’.second < ‘P[j]’.second and ‘i’ < ‘j’ but we don’t know anything about ‘P[i]’.first and ‘P[j]’.first. Now according to the greedy approach we should add ‘P[i]’ to our chain first. But why ?

Let’s check the following cases:

• If ‘P[i]’.second < ‘P[j]’.first then it is satisfying the condition that the next pair should have its first element greater than the second element of the current pair. So, we should add 'P[i]' to our chain before 'P[j]'.
• If ‘P[i]’.second >= ‘P[i]’.first now it is not satisfying the condition that means we can’t include both of them we either include ‘P[i]’ or ‘P[j]’ to our chain, also adding any one of them will increase the length by 1.
• But we should add ‘P[i]’ instead of ‘P[j]’ in our chain because ‘P[i]’.second < ‘P[j]’.second hence by making our chain ends at a smaller value will have a better probability to append more pairs.
• We traverse the sorted array and keep track of the ending value of the chain. Whenever we find a value that can be appended to our chain we will increment the length and update our chain end.
• Finally, we return the total length of the chain.