public int findLongestChain(int[][] pairs) {

if (pairs == null || pairs.length == 0) return 0;

Arrays.sort(pairs, (p1, p2) -> Integer.compare(p1[0], p2[0]));

int N = pairs.length;

int[] dp = new int[N + 1];

int res = 0;

for (int i=1; i<=N; i++) {

int local = 1;

for (int j=1; j<i; j++) {

if (pairs[i-1][0] > pairs[j-1][1] && dp[j] + 1 > local) {

local = dp[j] + 1;

}

}

dp[i] = local;

if (local > res) {

res = local;

}

}

return res;

}

public int findLongestChain2(int[][] pairs) {

if (pairs == null || pairs.length == 0) return 0;

Arrays.sort(pairs, (p1, p2) -> Integer.compare(p1[0], p2[0]));

LinkedList<int[]> list = new LinkedList<>();

for (int[] p: pairs) {

if (list.isEmpty() || list.getLast()[1] < p[0]) {

list.add(p);

} else {

if (p[1] < list.getLast()[1]) {

list.removeLast();

list.add(p);

}

}

}

return list.size();

}

public int findLongestChain3(int[][] pairs) {

if (pairs == null || pairs.length == 0) return 0;

Arrays.sort(pairs, (p1, p2) -> Integer.compare(p1[0], p2[0]));

int[] last = null;

int res = 0;

for (int[] p: pairs) {

if (last == null || last[1] < p[0]) {

last = p;

res++;

} else {

if (p[1] < last[1]) {

last = p;

}

}

}

return res;

}