Hey there and welcome back.
So in the previous videos we have discussed the list type dynamic programming questions.
Now over here let's do another question which is of the same type.
So let's go ahead and read the question.
And let's also discuss why this is an alias type question.
So let's get started.
The question is the maximum length of pair chain question.
The question reads you are given an array of n pairs where pairs I is equal to left I and right I.
So again it just says that each pair has two elements and left less than right.
So in each pair the value at the left position will be lower than the value at the right position.
A pair p two is equal to c comma d follows a pair p one, which is a comma b if b less than c.
So again what does this say over here.
So let's say you have two pairs a comma b and c comma d.
And if b is less than c then this pair over here follows this pair okay.
And these together make up a chain of pairs.
So it says over here a chain of pairs can be formed in this fashion.
Return the length of the longest chain which can be formed.
So that's the question.
We have to find the longest chain that can be formed.
And again the definition of a chain is given over here.
And we have to finally return the length of that particular chain, which is the longest chain that
can be formed.
You do not need to use up all the given intervals.
You can select pairs in any order.
So that's the question.
And we are given an example over here.
If the pairs array is this array over here.
And notice we have three pairs.
Now if this is the input array then the required output is equal to two.
Because we can only form a chain of pairs involving two elements.
So we have one comma two over here and four comma five over here.
And this is a valid pair because two is less than four.
And that's the condition which is given over here okay.
So in the question it's mentioned that we have to find the longest chain possible.
And we can select pairs in any order.
So that's why we are able to select one comma two before four comma five.
Because again that's not the order of the elements in the pairs array.
But that does not matter.
All right.
Now first let's discuss how can we identify that this question over here is a DP or a dynamic programming
question.
Now what are the hints given in the question that we can use to identify this?
Notice that in the question it says we have to find the length of the longest possible chain okay.
So that's asking for an optimal answer.
And then notice the question says we don't need to use up all the given intervals.
We can select pairs in any order.
So the question involves selection.
And it also asks us to find an optimal answer.
And these are two powerful hints which can help us to identify that this question over here is in fact
a dynamic programming question.
Now that we have identified this as a DP question, let's think about how we can identify the particular
type of this question.
And again, because in this course we are now dealing with less type questions.
We know that this is an alias type question.
But then how do we identify that in general?
Okay.
So notice that if we sort the array which is given to us over here, this pairs array, if we sort it
it would look like this.
So we have one comma two two comma nine and four comma five.
So again let's just say that we are sorting based on the first element.
Now we could do it even with the second element.
But over here let's just take a look at this approach where we are sorting based on the first element.
Now if we do that the array looks like this.
At this point.
And after we have done this, notice that we just need to find the longest increasing subsequence such
that b is less than c.
So over here we are trying to find a special type of increasing subsequence.
Now in the typical list question we have elements like this one, two and then five.
And then probably we have three and then we have seven.
Okay.
So we have elements in this manner in a typical list question.
And we need to find the increasing subsequence.
But over here we are not going to just consider every element.
We have a special condition that the second element in the first array over here has to be less than
the first element in the second array over here, or elements okay.
We can just call it as arrays or elements.
So we are just trying to find the length of the longest increasing subsequence with a special condition
or rule.
So that's why this is a dynamic programming question.
And more specifically it's a question of the list type.
Now in the next videos, let's go ahead and try to see how we can solve this question.
And when we write the code for solving this question, you will see how similar this question is to
a typical list question.
So let's get started.