跳到主要内容

Kite

· 阅读需 1 分钟

首先可以想到我们放置这个要，满足一个条件:若l1<l2l1\lt l2，则r1<r2r1\lt r2，否则产生重合

于是变为在先按照ll排序后寻找最长上升子序列，DPDP即可

AC代码
Details
#include<bits/stdc++.h>
using namespace std;
#define QAQ return
#define QWQ return 0;
#define ll long long
#define pii pair< int,int >

const int N=2e5+10;

struct seq
{
	int l, r;
	
	bool operator <( const seq &x )const
	{
		if( l == x.l ) QAQ r > x.r;
		QAQ l < x.l;
	}
	
}line[N];

int ans[N]; 

int main()
{
//	freopen( "txt.in","r",stdin );
//	freopen( "txt.out","w",stdout );
	ios::sync_with_stdio( false );
	cin.tie( nullptr ), cout.tie( nullptr );
	int n;
	cin>>n;
	for( int i=1;i<=n;i++ ) cin>>line[i].l>>line[i].r;
	sort( line+1,line+n+1 );
	int m=0;
	for( int i=1;i<=n;i++ )
	if( line[i].r > ans[m] ) ans[++m]=line[i].r;
	else                     ans[lower_bound( ans+1,ans+m+1,line[i].r )-ans]=line[i].r;
	cout<<m;
	QWQ
}

时间复杂度：O(nlogn)O(nlogn)