搭积木

// O(nlogn), O(n)
let num = readline()
num = parseInt(num)
let arr = []
while(line = readline()) {
    let [w, l] = line.split(' ')
    arr.push([parseInt(w), parseInt(l)])
}


// 1. sort by width increasing order
arr.sort((a,b) => {
    if (a[0] === b[0]) {
        return a[1] - b[1] // must do this also
    } else {
        return a[0] - b[0]
    }
})

// 2. find length of longest increasing subsequence (not continuous)
let nums = arr.map(i => i[1]) // get lengths
const lengthOfLIS = function(nums) {
    if (nums === null || nums.length === 0) return 0;
    if (nums.length === 1) return 1;
    let len = 0; // final ans
    
    let dp = new Array(nums.length).fill(0);
    for (let i = 0; i < nums.length; i++){
        let pos = binarySearchPosition(dp, nums[i], 0, len);
        dp[pos] = nums[i];
        if (pos === len) len++;
    }

    return len;
};

const binarySearchPosition = (dp, target, start, end) => {
    while (start < end) {
        let mid = Math.floor((start + end)/2);
        if (target >= dp[mid]) start = mid+1;
        else end = mid;
    }
    return end;
}

// print
print(lengthOfLIS(nums))