2402. Meeting Rooms III

[zeikar]

Problem link

https://leetcode.com/problems/meeting-rooms-iii

Problem Summary

미팅룸이 n개 있고 미팅 시간이 주어졌을 때 가장 미팅이 많이 한 룸을 구하는 문제.
미팅이 가능한 방이 여러개 있을 경우 가장 작은 번호의 방이 선택되며 현재 가능한 방이 없다면 가장 빠른 방을 사용한다.

Solution

그리디 방식으로 가능하다. 일종의 스케줄링 + 구현 문제라고 봐도 될 듯.
문제에 나온 그대로 작은 방부터 탐색하면서 미팅이 가능하면 미팅을 하면 된다. 시간 복잡도는 정렬을 포함해서 O(n * m log m) (사실 n이 최대 100이라 무시할 수 있다)

개선

다음 미팅 방을 뽑을 때 전체 순회가 아니고 priority queue를 사용하면 좀 더 줄일 수 있다.

Source Code

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        meetings = sorted(meetings, key=lambda item: item[0])
        rooms = [0] * n
        cnt = defaultdict(int)

        for meeting in meetings:
            min_room = 0
            for i in range(n):
                if rooms[i] <= meeting[0]:
                    min_room = i
                    break
                if rooms[min_room] > rooms[i]:
                    min_room = i
            
            if rooms[min_room] <= meeting[0]:
                rooms[min_room] = meeting[1]
            else:
                rooms[min_room] += (meeting[1] - meeting[0])
            cnt[min_room] += 1
        
        cnt = sorted(cnt.items(), key=lambda item: item[1], reverse=True)
        return cnt[0][0]