Greedy Activity Selection Algorithm

Question

I am trying to solve this problem: 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

I have come up with a greedy solution where I sort the classes by end time, then check if it's possible to allocate a class to an activity based on greedy conditions

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

However, this fails on a few (hidden) test cases.

Could someone point me in the right direction? What's the right approach to solve this problem?

Answer 1

Here's one example of how the current procedure could fail.

8 activities, 2 classrooms:

  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)

We can clearly see that the result could be 6, using the top and bottom tracks.

Here's the corresponding input:

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

I think a good avenue for exploration is along the lines you proposed except have k buckets (rather than just one) into which we'd like to keep choosing to create the next least end-time.