问题：有n 头牛（ 1<=n<=50,000) 要挤奶。给定每头牛挤奶的时间区间 [A,B]
(1<=A<=B<=1,000,000 A,B 为整数 。牛需要呆畜栏里才能挤奶。
一个畜栏同一时间只能容纳一头牛。问至少需要多少个畜栏，才能完成全部挤奶工作，
以及每头牛都放哪个畜栏里（ Special judged)去同一个畜栏的两头牛，
它们挤奶时间区间哪怕只在端点重合也是不可以的。
现在农场主希望知道最少几个畜栏能满足上述要求，并要求给出每头牛被安排的方案。
对于多种可行方案，主要输出一种即可。输入：
输入的第一行包含一个整数N(1 ≤ N ≤ 50, 000)，表示有N牛头；接下来N行
每行包含两个数，分别表示这头牛的挤奶时间[Ai, Bi](1≤A≤B≤1,000,000)。
输出：
输出的第一行包含一个整数，表示最少需要的畜栏数；接下来N行，第i+1行描述了
第i头牛所被分配的畜栏编号（从1开始）。样例输入
5
1 10
2 4
3 6
5 8
4 7
样例输出
4
1
2
3
2
4思路：贪心解法，所有奶牛都必须挤奶。到了一个奶牛的挤奶开始时间，就必须为这个奶
牛找畜栏。因此按照奶牛的开始时间逐个处理它们，是必然的。S(x)表示奶牛x的开始时间。
E(x) 表示 x 的结束时间。对 E(x), x 可以是奶牛，也可以是畜栏。
畜栏的结束时间，就是正在其里面挤奶的奶牛的结时间。
同一个畜栏的结束时间是不断在变的。1)把所有奶牛按开始时间从小到大排序。
2)为第一头奶牛分配一个畜栏。
3)依次处理后面每头奶牛i。处理 i 时，考虑已分配畜栏中，结束时间最早的畜栏x。
若E(x) < S(i), 则不用分配新畜栏，i可进入x,并修改 E(x)为 E(i)
若E(x) >= S(i)，则分配新畜栏 y,记 E(y) = E(i)
直到所有奶牛处理结束
需要用优先队列存放已经分配的畜栏，并使得结束时间最早的畜栏始终位于队列头部。
从第一头奶牛开始，第一头奶牛肯定放进第一个牛栏里，之后每个奶牛都是与牛栏中
结束时间最早的那个相比，如果可以放进去，就放进去啦，如果不能放进去，就重新开一个牛栏由于按开始时间的顺序处理奶牛是必然，且按该算法，为奶牛
i 分配新畜栏时，确实是不得不分配的，所以算法正确。python代码实现：
from queue import PriorityQueue def main(): # 输入牛的列表，0：起始时间，1：结束时间，2：牛的编号 cow_list = [] # 总共需要的畜栏 total = 0 # i表示编号为i的奶牛去的畜栏编号 pos = [0 for i in range(10)] # n头牛 n = int(input()) for i in range(1, n+1): temp = list(map(int, input().split())) temp.append(i) cow_list.append(temp) cow_list = sorted(cow_list, key=lambda x: x[0]) # 按开始时间排序后的列表 # [[1, 10, 1], [2, 4, 2], [3, 6, 3], [4, 7, 5], [5, 8, 4]] # pq优先权队列中元素是list，0：结束时间，1：畜栏编号 pq = PriorityQueue() for i in range(n): if pq.empty(): total += 1 pq.put([cow_list[i][1], total]) pos[cow_list[i][2]] = total else: # 获取pq队列中结束时间最早的列表st # st = pq.get() # 此处很重要，如果使用get会把队头元素删除，使用queue属性，则会返回 # 整个队列元素的列表，为了去队头，所以索引是0 st = pq.queue[0] # 队列中最早结束时间小于新加入这头牛的开始时间 if st[0] < cow_list[i][0]: pos[cow_list[i][2]] = st[1] pq.put([cow_list[i][1], st[1]]) # 新增加一个牛栏 else: total += 1 pq.put([cow_list[i][1], total]) pos[cow_list[i][2]] = total print("最少需要的畜栏数:%d" % total) for i in range(1, n+1): print("%d" % pos[i]) return 0 if __name__ == '__main__': main()
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。