C++14(g++5.4) 解法, 执行用时: 615ms, 内存消耗: 26468K, 提交时间: 2020-06-23 15:27:26

#include <bits/stdc++.h>
using namespace std;

const int MAXN=1e6+10;
struct node{
    int s,e;
    bool operator < (const node a)const{
        return s==a.s?e<a.e:s<a.s;
    }
}arr[MAXN];
int n,k;
multiset<int> st;

int main(){
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)scanf("%d%d",&arr[i].s,&arr[i].e);
    sort(arr,arr+n);
    int res=0;
    for(int i=0;i<n;i++){
        if(!st.empty() && *st.begin()<arr[i].s)st.erase(st.begin());
        if(st.size()<k)st.insert(arr[i].e);
        else{
            res++;
            st.insert(arr[i].e);
            st.erase(--st.end());
        }
    }
    printf("%d",res);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 1250ms, 内存消耗: 59344K, 提交时间: 2020-06-26 10:30:13

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e6+10;

multiset<int> s;
vector<int> t[maxn];

int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
	for( int i=1;i<=n;i++ )
	{
		int l,r;scanf("%d%d",&l,&r);
		t[l].push_back(r);
	}
	int ans=0;
	for( int i=1;i<=1e6;i++ )
	{
		while( !s.empty() && *s.begin()<i ) s.erase(s.begin());
		for( auto it:t[i] )
		{
			if( s.size()<k ) s.insert(it);
			else 
			{
				ans++;
				s.insert(it);
				s.erase(--s.end());
			}
		}
	}
	printf("%d\n",ans);
}