C++(g++ 7.5.0) 解法, 执行用时: 702ms, 内存消耗: 19488K, 提交时间: 2023-03-27 09:41:30

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>

using namespace std;

#define out(x) cout << #x << '=' << x << endl
#define out2(x, y) cout << #x << '=' << x << ',' << #y << '=' << y << endl 
#define no cout << "No" << endl; return
#define yes cout << "Yes" << endl; return
#define outvec(a) for (auto &v : a) { cout << v << ' '; } cout << endl
#define lowbit(x) (x & -x)
#define gcd __gcd 
#define inf 0x3f3f3f3f3f3f3f3fLL
#define infi 0x3f3f3f3f

using ll = long long;
using pii = pair<int, int>;

 

void solve() {
	int n;
    cin >> n ;
    vector<pii> v(n + 1);
    vector<int> p;
    for (int i = 1; i <= n; i++) {
        cin >> v[i].first >> v[i].second;
        p.push_back(v[i].first);
        p.push_back(v[i].second);
    }
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    vector<int> dp(p.size());
    sort(v.begin(), v.end(), [&](pii a, pii b) -> int {
        return a.second < b.second;
    });
    int j = 1;
    auto index = [&](int x) -> int {
        return lower_bound(p.begin(), p.end(), x) - p.begin();
    };
    for (int i = 0; i < p.size(); i++) {
        if (i) dp[i] = dp[i - 1];
        while (j <= n && index(v[j].second) == i) {
            dp[i] = max(dp[i], dp[index(v[j].first)] + 1);
            j++;
        }
    }
    cout << dp[p.size() - 1] << endl;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t = 1;
	//cin >> t;
    
    while (t--) {
    	solve();
	}
}

Java 解法, 执行用时: 3769ms, 内存消耗: 59004K, 提交时间: 2023-05-23 17:20:31

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = sc.nextInt();
        int[][] vec = new int[n][2];
        for (int i = 0; i < n; i++) {
            vec[i][0] = sc.nextInt();
            vec[i][1] = sc.nextInt();
        }
        Arrays.sort(vec,(a,b)->a[1]-b[1]);
        int res = 1,end = vec[0][1];
        for (int i = 1; i < n; i++) {
            if(vec[i][0]>=end){
                res++;
                end = vec[i][1];
            }
        }
        System.out.println(res);
    }
}

C++14(g++5.4) 解法, 执行用时: 1028ms, 内存消耗: 8184K, 提交时间: 2020-01-22 23:38:04

#include<bits/stdc++.h>
using namespace std;
pair<int,int>a[1000005];
int main(){
	int i,j,m,n,k=0,result=1;
	cin>>n;
	for(i=0;i<n;i++)
		cin>>a[i].second>>a[i].first;
	sort(a,a+n);	
	for(i=0;i<n;i++)
		if(a[i].second>=a[k].first){
		k=i;
		result++;
		}
	cout<<result;	
	return 0;
}
 

C++11(clang++ 3.9) 解法, 执行用时: 853ms, 内存消耗: 8296K, 提交时间: 2020-03-13 11:16:29

#include<bits/stdc++.h>
using namespace std;
pair<int,int>a[1000005];
int main()
{
	int i,j,m,n,k=0,result=1;
	cin>>n;
	for(i=0;i<n;i++)
	cin>>a[i].second>>a[i].first;
	sort(a,a+n);
	for(i=0;i<n;i++)
	if(a[i].second>=a[k].first)
	{
		k=i;
		result++;
	}
	cout<<result;
	return 0;
}