题解

#include<iostream>
#include<algorithm>
using namespace std;
struct time{	
	int begin,end;
}a[10005];
int cmp(struct time a1,struct time a2){  
		if(a1.end!=a2.end)
	      return a1.end<a2.end;
	    if(a1.begin!=a2.begin)
	      return a1.begin<a2.begin;
}
int read(){
    int x = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9'){
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9'){
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * w;
}
int main(){
	int n,p,m,dp[30005]={0};	
	n=read();
	for(int i=0;i<n;i++){
	   a[i].begin=read();
	   a[i].end=read();
	}
	sort(a,a+n,cmp);
	p=a[n-1].end;
	for(int i=0;i<n;i++){
		for(int j=p;j>=a[i].end;j--){
			dp[j]=max(dp[j],dp[a[i].begin]+a[i].end-a[i].begin);
		}
	}
	cout<<dp[p];	
	return 0;
}