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?