# easy dp

• ``````    public int findLongestChain(int[][] pairs) {
if (pairs == null || pairs.length == 0) return 0;
Arrays.sort(pairs, (a, b) -> (a[0] - b[0]));
int[] dp = new int[pairs.length];
Arrays.fill(dp, 1);
for (int i = 0; i < dp.length; i++) {
for (int j = 0; j < i; j++) {
dp[i] = Math.max(dp[i], pairs[i][0] > pairs[j][1]? dp[j] + 1 : dp[j]);
}
}
return dp[pairs.length - 1];
}
``````

• @Yang_BU
Very clear even for me, thanks

• Same idea in python cannot get accepted.

• There is one problem called "Russian Doll Envelop" which used a binarysearch to optimize the double loop. Those two problem look similar to each other. Im wondering if that technique can be used here, as well. For now, I'm still thinking.

• Yes. Definitely so. I solved this by using the binary search method.

• dp and greedy
dp
sort it with a[0] or a[1], in fact they are equal, then LIS

``````class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {

int n = pairs.size();
sort(pairs.begin(), pairs.end(), cmp);
vector<int> dp(n,0);
if(n==0)
return 0;
dp[0] = 1;
int max_len = 1;
for(int i=1;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(pairs[i][0]> pairs[j][1])
dp[i] = max(dp[i],dp[j]+1);
}
max_len = max(max_len,dp[i]);
}
return max_len;
}
private:
static bool cmp(vector<int>& a, vector<int>& b)
{
return a[1] < b[1];
}

};
``````

greedy
sort it with a[0]

``````class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {

int n = pairs.size();
sort(pairs.begin(), pairs.end(), cmp);
int count  = 0;
int cur_end = INT_MIN;
for(int i=0;i<n;i++)
{
if(pairs[i][0] > cur_end)
{
count ++;
cur_end = pairs[i][1];
}

else if(pairs[i][1] < cur_end)
cur_end = pairs[i][1];
}
return count;

}
private:
static bool cmp(vector<int>& a, vector<int>& b)
{
return a[0] < b[0];
}

};
``````

• @Herculescn i also thought of that solution (Binary search) wonder if u have came up with that solution already?

• @yuhaok yes, I did. If you need, I can paste my accepted solution here. It only beats 69.23%, though.

• Just like longest increasing sequence.

``````    public int findLongestChain(int[][] pairs) {
int n  = pairs.length;
Arrays.sort(pairs, (a , b)->{
if(a[0] == b[0]){
return a[1] - b[1];
} else {
return a[0] - b[0];
}
});

int[] dp = new int[n];
Arrays.fill(dp, 1);

for(int i = 0; i < n; i++){
for(int j = 0; j < i; j++){
if(pairs[j][1] < pairs[i][0]){
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}

return dp[n - 1];
}``````

• python fails to pass with dp, sad

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