For a sequence \(X = (x_1,\ldots,x_N)\) with around \(2 \times 10^5\) elements, we can find the LIS as follows (the settings are slightly modified from usual to be used in the following solution).

• For \(1 \leq i \leq N\), let \(\mathrm{dp}_i\) be the smallest value of the last element of a length-\(i\) strictly increasing subsequence.
• For \(i=1,2,\ldots,N\) in this order, find the smallest \(j\) such that \(\mathrm{dp_j} \geq x_i\) with binary search, and update \(\mathrm{dp_j}\) to \(x_i\).
• The answer is the number of indices \(i\) such that \(\mathrm{dp_i} \neq \mathrm{Inf}\) in the end.

Let us apply this to our problem. Consider a length-\(10^9\) binary sequence whose \(x\)-th element is \(1\) if there is \(i\) such that \(\mathrm{dp}_i =x \) and \(0\) otherwise. Then, for \((l_i,r_i)\), we need to change to \(0\) at most \((r_i-l_i+1)\) \(1\)s from the left whose indices are at least \(l_i\), and change to \(1\) the \(l_i\)-th through \(r_i\)-th elements. One can simulate this process in \(\mathrm{O}(N \log N)\) time in total by compressing the indices and then using a lazy segment tree that supports ranged update and addition.
Alternatively, one can use map to maintain segments in the array \(\mathrm{dp}\) whose values increase by \(1\) from left to right like \(5,6,7,\ldots\) to find the answer fast enough.

Sample Implementation (C++)

#include <bits/stdc++.h>
#include <atcoder/lazysegtree>
using namespace atcoder;
using namespace std;

pair<int,int> op(pair<int,int> a,pair<int,int> b){
	a.first += b.first;
	a.second += b.second;
	return a;
}

pair<int,int> e(){
	return make_pair(0,0);
}

pair<int,int> mapping(int a,pair<int,int> b){
	if(a==-1)return b;
	b.first = b.second * a;
	return b;
}

int composition(int a,int b){
	if(a==-1)return b;
	return a;
}

int id(){
	return -1;
}

int X;
bool f(pair<int,int> x){
	return x.first<=X;
}

int main() {
	
	int N;
	cin>>N;
	
	vector<int> l(N),r(N);
	vector<int> t;
	for(int i=0;i<N;i++){
		cin>>l[i]>>r[i];
		r[i]++;
		t.push_back(l[i]);
		t.push_back(r[i]);
	}
	
	sort(t.begin(),t.end());
	t.erase(unique(t.begin(),t.end()),t.end());
	
	vector<pair<int,int>> temp;
	for(int i=0;i<t.size()-1;i++){
		temp.emplace_back(0,t[i+1]-t[i]);
	}
    
	lazy_segtree<pair<int,int>,op,e,int,mapping,composition,id> seg(temp);
	
	for(int i=0;i<N;i++){
		int il = distance(t.begin(),lower_bound(t.begin(),t.end(),l[i]));
		int ir = distance(t.begin(),lower_bound(t.begin(),t.end(),r[i]));
		X = r[i]-l[i];
		
		int rr = seg.max_right<f>(il);
		X -= seg.prod(il,rr).first;
		seg.apply(il,rr,0);
		
		if(rr!=temp.size()){
			auto g = seg.get(rr);
			g.first -= X;
			seg.set(rr,g);
		}
		
		seg.apply(il,ir,1);
	}
	
	cout<<seg.all_prod().first<<endl;
	
    return 0;
}