贪心Activity选择算法

Question

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

There are classrooms on campus and proposed activities that need to be assigned a venue. Every proposed activity has specfic starting time and ending time . Any such an activity should take place at one of the classrooms. Any of the classrooms is big enough to hold any of the proposed activities, and each classroom can hold at most one activity at any time. No two proposed activities can take place at the same classroom at the same time. Even if two proposed activities overlap momentarily (the ending time of one activity equals the starting time another activity), they cannot be assigned to the same classroom.

There are so many proposed activities that there may not be enough classrooms to hold all the activities. It is desirable to have as many activities as possible. At most how many proposed activities can be assigned to the classrooms?

Input The first line contains two positive integers and (1≤≤≤200000), representing the number of proposed activities and number of classrooms, respectively.

The following lines each contains two positive integers: the th line among these lines contains and (1≤≤≤109), indicating the starting time and ending time of proposed activity

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

'''
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)

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

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

Answer 1

这是当前过程可能失败的一个示例。

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，使用顶部和底部轨道。

这是相应的输入：

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

贪心Activity选择算法

Greedy Activity Selection Algorithm

python

algorithm

greedy