package question;

import java.util.Arrays;

/**
 * @author Roderland
 * @since 1.0
 */
public class Question354 {
 public static void main(String[] args) {
 System.out.println(new Question354().maxEnvelopes(new int[][]{
 {1, 3}, {3, 5}, {6, 7}, {6, 8}, {8, 4}, {9, 5}
 }));
 }
 // 1 3 6 6 8 9
 // 3 5 7 8 4 5


 public int maxEnvelopes(int[][] envelopes) {
 // 长度升序,宽度降序
 Arrays.sort(envelopes, (o1, o2) -> o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0]);
 // 最长递增子序列
 int[] res = new int[envelopes.length];
 int len = 0;
 for (int[] num : envelopes) {
 int index = Arrays.binarySearch(res, 0, len, num[1]);
 index = index < 0 ? -index - 1 : index;
 res[index] = num[1];
 if (index == len) len++;
 }
 return len;
 }
}