贪心 + 小根堆

很自然, 按照吃草的先后顺序来安排奶牛, 将奶牛按照吃草的起始时间来排序.
安排当前奶牛的时候, 观察一下现在是否有空置的畜栏, 如果有, 随意安排到其中一个, 如果没有, 新建一个畜栏.
观察现在是否有空置的畜栏, 需要用到小根堆. 小根堆里保存的畜栏里面奶牛吃草结束时间. 如果现在的时间 > 堆顶的时间, 那么堆顶可以出堆了, 将堆顶保存到empty容器里面, empty表示当前所有空置的畜栏的编号.

时间复杂度

排序时间复杂度为O(Nlog(N))
每个元素入堆一次, 出堆1次或者0次. 每次入堆或出堆的时间复杂度为O(log(畜栏的平均个数)), 而畜栏的平均个数 <= N的, 因此, 这个操作的最差时间复杂度为O(N * log(N))
总体的时间复杂度为O(Nlog(N))

Python 代码

from heapq import heappop, heappush

N = int(input())
Cows = []
for i in range(N):
    a, b = map(int, input().split())
    Cows.append((a, b, i))
Cows.sort()
H = []
empty = []
ans = [0] * N
cnt = 0
for i in range(N):
    a, b, ii = Cows[i]
    while H and H[0][0] < a:
        _, idx = heappop(H)
        empty.append(idx)
    if not empty:
        idx = len(H)
        ans[ii] = (idx + 1)
        heappush(H, (b, idx))
        cnt = idx + 1
    else:
        idx = empty.pop()
        ans[ii] = (idx + 1)
        heappush(H, (b, idx))
print(cnt)
for e in ans:
    print(e)