C++(g++ 7.5.0) 解法, 执行用时: 129ms, 内存消耗: 12812K, 提交时间: 2022-10-31 21:17:45

 #include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int f[N];
int n;
map<int,int>sum[N];
vector<int>temp[N];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int a,b;
       cin>>a>>b;
        int l=a+1,r=n-b;
        if(l>r) continue;
        if(!sum[l][r])
        temp[r].push_back(l);
        sum[l][r]=min(r-l+1,sum[l][r]+1);
    }
    
    for(int i=1;i<=n;i++)
    {
        f[i]=f[i-1];
        for(int j=0;j<temp[i].size();j++)
        {
            f[i]=max(f[temp[i][j]-1]+sum[temp[i][j]][i],f[i]);
        }
    }
    cout<<n-f[n]<<endl;
    
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 250ms, 内存消耗: 18368K, 提交时间: 2022-10-11 22:50:51

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
typedef pair<int,int> PII;
map<PII,int> mp1;
map<int,set<int>> mp2;
int f[N];
signed main()
{
    int n;    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int a,b;    cin>>a>>b;
        int l = a+1, r = n-b;
        mp2[r].insert(l);
        mp1[{l,r}]++;
    }
    
    for(int i=1;i<=n;i++)
    {
        f[i] = f[i-1];
       for(auto l : mp2[i])
       {
           f[i] = max(f[i],f[l-1] + min(mp1[{l,i}],i-l+1));
       }
    }
    cout<<n-f[n]<<endl;
}