https://www.acmicpc.net/problem/11000
initial
I was surprised that I got the general approach right. We use heap to store the meeting room’s ending time and as we iterate through the meetings, if the meeting room’s ending time is greater or equal to current meeting’s start time, we can continue to use this meeting room without adding another one via changing that meeting room’s end time to current meeting’s end time. Else we have to add another meeting room.
But I wrongly implemented like we dont have to iter each element in our heap, causing runtime ineff. code.
Oh so i know why we dont have to iter for each end time stored in our heap, making solution n^2 time. Cuz we know the first element in our heap will store the earliest ending time that our meeting room is gonna be available. And if we know even that earliest time is still earlier than the current meeting’s end time, then theres no point checking the other meeting rooms’ ending time in our heap cuz it surely will not meet the condition.
revisited feb 23rd
strangely i couldnt think of heap lol maybe cuz im distracted in office
but we store the meeting ending time, initialised with the earliest ending time by sorting the given list with key=lambda x:x[1]. Then, if incoming meetings start later or right at the same time as this end time, then we can continue to use this meeting room. So we update our heap by popping and appending with this new meeting start and end time. Else, we need to create another meeting room so we append the meeting to our heap. Heap will ensure that the 0th element we are looking at has the earliest ending time.
solution
import sys
import heapq
input=sys.stdin.readline
n = int(input())
lst = []
for _ in range(n):
a, b = map(int, input().split())
lst.append([a, b])
lst.sort(key=lambda x: x[0])
room = [lst[0][1]]
heapq.heapify(room)
for i in range(1, n):
start, end = lst[i]
if room[0] <= start:
heapq.heappop(room)
heapq.heappush(room, end)
print(len(room))complexity
was heap operations log n?
so n log n? yea we also have sort so def
Time Complexity:
The time complexity is primarily determined by the sorting step and the iteration through the meetings. Sorting the meetings by their start times has a time complexity of O(N log N), where N is the number of meetings.
The subsequent iteration through the sorted meetings has a linear time complexity of O(N).
Overall, the time complexity is dominated by the sorting step, and the final time complexity is O(N log N).
Space Complexity:
The space complexity is influenced by the data structures used, mainly the priority queue (room), and the input data (the list of meetings).
The room priority queue stores the end times of ongoing meetings. In the worst case, it may store all end times, resulting in a space complexity of O(N).
The input data structure (lst list) stores the start and end times of all meetings. The space complexity is O(N) for the input data.
The overall space complexity is O(N), considering both the priority queue and the input data.
In summary:
Time Complexity: O(N log N)
Space Complexity: O(N)
