C++14(g++5.4) 解法, 执行用时: 23ms, 内存消耗: 1388K, 提交时间: 2020-05-10 17:47:40

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
typedef pair<int,int>pii;
int n,k,sum[N];

pair<pii,int> a[N];
priority_queue<pii,vector<pii>,greater<pii> >q;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i].first.first,&a[i].first.second);
		a[i].second=i;
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++)
	{
		if(q.empty()||q.top().first>=a[i].first.first)
		{
			sum[a[i].second]=q.size()+1;
			q.push({a[i].first.second,q.size()+1});
		}
		else {
			 auto t=q.top();
			 q.pop();
			 sum[a[i].second]=t.second;
			 t.first=a[i].first.second;
			 q.push(t);
		}
	}
	printf("%d\n",q.size());
	for(int i=1;i<=n;i++)
	printf("%d\n",sum[i]);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 154ms, 内存消耗: 1508K, 提交时间: 2020-03-04 10:25:10

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int st,ed,id;
}cow[50005];
int a[50005],b[50005];
bool cmp(node a,node b)
{
	return a.st<b.st;
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>cow[i].st>>cow[i].ed;
		cow[i].id=i;
	}
	sort(cow+1,cow+n+1,cmp);
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		int f=0;
		for(int j=1;j<=cnt;j++)
		{
			if(a[j]<cow[i].st)
			{
				a[b[cow[i].id]=j]=cow[i].ed;
				f=1;
				break;
			}
		}
		if(!f) a[b[cow[i].id]=++cnt]=cow[i].ed;
	}
	cout<<cnt<<endl;
	for(int i=1;i<=n;i++) cout<<b[i]<<endl;
	return 0;//程序拜拜 
}

pypy3(pypy3.6.1) 解法, 执行用时: 263ms, 内存消耗: 32360K, 提交时间: 2021-05-05 22:48:39

from heapq import *

n=int(input())  # 牛数
s=[]            # [开始t,结束t,牛编号]
for i in range(n):
    a,b=map(int, input().split())
    s.append([a,b,i+1])

# 按牛开始吃草时间升序
s.sort(key=lambda s:s[0])


cl=[[s[0][1] ,1]] 
num=1

z=[] # [牛编号，牛所在栏]
z.append([s[0][2],1])

for i in range(1,n):
    a,b,index=s[i]

    if a>cl[0][0]:
        z.append([index, cl[0][1]])
        heappushpop(cl, [b, cl[0][1]])
    else:
        num+=1
        z.append([index, num])
        heappush(cl, [b, num])

z.sort(key=lambda z:z[0])
print(num)
for i in z:
    print(i[1])

Python3 解法, 执行用时: 364ms, 内存消耗: 12672K, 提交时间: 2023-07-11 20:26:06

N=int(input())
arr=[]
for i in range(N):
    arr.append(list(map(int,input().split()))+[i])
import heapq
heap=[]
arr.sort()
ans=[1]*N 
heapq.heappush(heap,[arr[0][1],1])
cnt=1
#ans[arr[0][-1]]=1
for i in range(1,N):
    if arr[i][0]>heap[0][0]:
        q=heapq.heappop(heap)
        ans[arr[i][-1]]=q[1]
        heapq.heappush(heap,[arr[i][1],q[1]])
    else:
        cnt+=1
        ans[arr[i][-1]]=cnt 
        heapq.heappush(heap,[arr[i][1],cnt])
print(cnt)
for i in ans:
    print(i)