python小根堆实现贪心算法
本题比较直观的思路就是对数组遍历一遍,遇到一头牛的吃草起始时间比已经放到畜栏中的牛的吃草最晚时间还要大的时候,就可以合并了,反之就添加到新的畜栏中.
那么我们需要保证在对数组遍历之前,数组就已经按照每头牛的吃草起始时间从小到大排序了.为什么这么说呢?不妨用样例来证明.样例中有[2, 4]与[5, 8]两组数据,显然可以合并.但如果改一下顺序呢,换成[5, 8]与[2, 4],这样在遍历过程中,第二头牛的吃草起始时间就已经比之前牛的最小的最晚吃草时间都要小了,就应该添加到新的畜栏中,这样明显是不对的.因此需要先对数组进行排序.
第二个问题就是怎么找到需要合并的畜栏?即怎么找到之前遍历过的牛的最小的最晚吃草时间?如果再用一层for循环来找的话,时间复杂度就到了n^2,这样会超时.那么就可以采用小根堆来做,能够达到nlogn的时间复杂度.用小根堆来维护所有遍历过的牛的最小最晚吃草时间即可.
接下来就是遍历比较了,每遍历到一头牛,都要与小根堆堆顶的最晚吃草时间比较,若该牛的最早吃草时间要大的话,那么直接合并即可.合并的操作就是将小根堆堆顶的元素弹出,更新新的最晚吃草时间即可.
python代码
import heapq
N = int(input())
cows = []
for i in range(N):
a, b = map(int, input().split())
cows.append([a, b, i])
heap = [] #创建小根堆,存储空闲畜栏
cows.sort() #按吃草起始时间排序
ans = [0] * N #记录每头牛的方案序号
for i in range(N):
cow_a = cows[i][0] #保存遍历牛吃草的起始时间用于比较
if not heap or cow_a <= heap[0][0]: #若当前没有畜栏,或者当前牛的起始吃草时间晚于畜栏的最晚吃草时间,即不能合并时需创建新的畜栏
idx = len(heap) + 1
stall = [cows[i][1], idx] #保存最晚吃草时间以及方案序号
ans[cows[i][2]] = idx
heapq.heappush(heap, stall)
else: #需要合并
stall = heap[0]
idx = stall[1]
ans[cows[i][2]] = idx
heapq.heappop(heap)
stall[0] = cows[i][1]
heapq.heappush(heap, stall)
print(len(heap))
for i in range(N):
print(ans[i])