カササギ橋の長さ

質問:
@陳利人
カササギがn対いる.各ペアは(x,y)と表すことができ、x,yはカササギの番号であり、任意のペアでは、xは常にyより小さい.(c,d)は、(a,b)の後に接続され、bのみ
PS:ここのカササギ橋の長さはつながっているカササギの個数です.
分析I:
2 Dでは、エッジ長が1のトポロジーマップ(有向図)を構築し、最長パスを見つけることができます.
時間複雑度O(n^2).
分析II:
1次元では、まずカササギをx順に並べ替え、length[i]でi~n番目のカササギで建てられる最長の長さを表す.では、
length[ i ] = max{length[ i+1 ],1 + length[ j ]},
ここでjはj>i,v[j]を満たす.x > v[i].yの最小下付き文字、すなわちj=min{k|k>i,v[k].x>v[i].y}である.二分法を用いてlog(n)時間内にjを決定することができる.
時間複雑度O(nlogn).空間複雑度O(n).
コード:

struct Magpie{
	int x, y;
};
int getPieBridgeLength(vector &v){
	if(v.empty())	return 0;
	std::sort(v.begin(), v.end(), 
		[](const Magpie &m1, const Magpie &m2){return m1.x < m2.x;});
	vector len(v.size(), 0);
	for(int i = len.size() - 1; i >= 0; --i){
		auto it = std::upper_bound(v.begin()+i, v.end(), v[i].y, 
			[](int a, const Magpie &m){return a < m.x;});
		len[i] = std::max(it == v.end()? 1 : 1 + len[it - v.begin()],  
			i+1 >= len.size() ? 0 : len[i+1]);
	}
	return len[0];
}

テストコード:

int main() {
	Magpie arr[] = {{1,3}, {7,10}, {4,5}, {2,4}};
	vector v(begin(arr), end(arr));
	cout << getPieBridgeLength(v) << endl;
	return 0;
}