时间戳

首页 > 解决方案 > 贪心活动选择算法

python - 贪心活动选择算法

问题描述

我正在尝试解决这个问题：https ://open.kattis.com/problems/classrooms

校园内有教室和需要分配场地的拟议活动。每个提议的活动都有特定的开始时间和结束时间。任何此类活动都应在其中一间教室进行。任何一个教室都足够大，可以举办任何提议的活动，而且每个教室在任何时候最多可以举办一个活动。没有两个提议的活动可以同时在同一个教室里进行。即使两项提议的活动暂时重叠（一项活动的结束时间等于另一项活动的开始时间），也不能将它们分配到同一个教室。

提议的活动太多，可能没有足够的教室来举办所有的活动。希望有尽可能多的活动。最多可以为教室分配多少建议的活动？

输入 第一行包含两个正整数和（1≤≤≤200000），分别代表提议活动的数量和教室的数量。

以下各行包含两个正整数：第1行包含and(1≤≤≤109)，表示提议活动的开始时间和结束时间

我想出了一个贪婪的解决方案，我按结束时间对类进行排序，然后检查是否可以根据贪婪条件将类分配给活动

'''
https://open.kattis.com/problems/classrooms
'''

from collections import deque

n, k = map(int, input().split())
classes = []
for _ in range(n):
    (start, end) = map(int, input().split())
    classes.append((start, end))

classes.sort(key=lambda x: x[1])
queue = deque()
count = 0
for (start, end) in classes:
    if queue and queue[0] < start:
        queue.popleft()
        queue.append(end)
        count += 1
    elif len(queue) < k:
        count += 1
        queue.append(end)
print(count)

但是，这在一些（隐藏的）测试用例上失败了。

有人能指出我正确的方向吗？解决这个问题的正确方法是什么？

标签： pythonalgorithmgreedy

解决方案

这是当前程序如何失败的一个示例。

8 项活动，2 间教室：

  a   b   c
 --- --- ------
 d     e
--- -------
  --- ---- ---
   f   g   h

queue   count
 d       1
 d a     2
 f (no)
 a b     3
 b g     4
 e (no)
 g h     5
 c (no)

我们可以清楚地看到结果可能是 6，使用顶部和底部轨道。

这是相应的输入：

8 2
2 4
6 8
10 15
1 3
5 11
3 5
7 10
12 14

我认为一个很好的探索途径是沿着你提出的路线，除了有 k 个桶（而不仅仅是一个），我们希望继续选择在其中创建下一个最短结束时间。

推荐阅读