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)