https://leetcode.com/problems/meeting-rooms-iii/
Meeting Rooms III - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
리트코드 Hard 난이도 문제. 얼마전에 봤던 모 회사 면접문제에 출제되었던 알고리즘 문제이다.
문제
You are given an integer n. There are n rooms numbered from 0 to n - 1.
You are given a 2D integer array meetings where meetings[i] = [starti, endi] means that a meeting will be held during the half-closed time interval [starti, endi). All the values of starti are unique.
Meetings are allocated to rooms in the following manner:
- Each meeting will take place in the unused room with the lowest number.
- If there are no available rooms, the meeting will be delayed until a room becomes free. The delayed meeting should have the same duration as the original meeting.
- When a room becomes unused, meetings that have an earlier original start time should be given the room.
Return the number of the room that held the most meetings. If there are multiple rooms, return the room with the lowest number.
A half-closed interval [a, b) is the interval between a and b including a and not including b.
회의실의 개수 n이 정수로 주어지는데, 회의실 방 번호는 0번부터 n-1까지 이루어져있다.
그리고 2차원 정수 배열도 주어지는데, meetings[i] = [시작시간i, 끝시간i] 정보가 들어가 있다. 시작시간부터 끝시간 전까지 회의가 이루어진다. 즉, [시작시간i, 끝시간i)인데, 시작시간은 회의에 포함되지만 끝시간은 회의에 포함되지 않는다. 그리고 시작시간i은 중복되지 않는다.
회의는 아래와 같은 방식을 따라서 이루어진다.
- 각 회의는 사용하지 않는 회의실 중 가장 작은 번호의 회의실에서 이루어진다.
- 만약 사용할 수 있는 회의실이 없다면, 사용할 수 있는 방이 생길때까지 회의는 미뤄진다. 회의가 미뤄져도 회의가 진행되는 시간은 변경되지 않는다. (즉, 1시부터 3시간동안 진행 예정이었던 회의가 3시로 밀린다면 3시부터 3시간 진행됨)
- 회의실이 비게 되는 경우, 원래 잡혀있던 시간 중 빠른 시간 순서대로 회의를 매칭해준다.
이때, 가장 많이 회의가 열린 방의 번호를 정답으로 제출하면 된다. 만약 여러개의 방이 공동 1등을 한다면, 가장 작은 방의 번호를 정답으로 제출하라.
예시
Input: n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
Output: 0
Explanation:
- At time 0, both rooms are not being used. The first meeting starts in room 0.
- At time 1, only room 1 is not being used. The second meeting starts in room 1.
- At time 2, both rooms are being used. The third meeting is delayed.
- At time 3, both rooms are being used. The fourth meeting is delayed.
- At time 5, the meeting in room 1 finishes. The third meeting starts in room 1 for the time period [5,10).
- At time 10, the meetings in both rooms finish. The fourth meeting starts in room 0 for the time period [10,11).
Both rooms 0 and 1 held 2 meetings, so we return 0.
문제 풀이
나의 경우는 우선 실제로 손으로 문제를 푼 다음, 그걸 코드로 옮겨 적는 편이다.
만약에 실제로 이런 문제를 해결해야한다면, 현실에서는 어떻게 풀까?
먼저 회의 예약 스케쥴을 시간 순서대로 다시 정렬할 것이다. (input으로 당연히 정렬해서 줄거라고 믿지말자. ㅋㅋ)
그리고 회의실별로 타임테이블을 그린 후에 회의를 순서대로 배정해볼것이다.
우선 예시에 대해서 아래와 같이 초기 세팅을 한다.
맨 처음 회의는 시간 0부터 10까지 진행되는 회의이다. 사용할 수 있는 회의실이 있고, 0번 회의실이 비어있으니 여기에 배정을 해준다.
그리고 두번째 회의는 시간 1부터 5까지 진행되는 회의이다. 0번 회의실은 사용중이지만 1번 회의실이 사용 가능하니 거기에 회의를 배정해준다.
그 다음 회의는 시간 2부터 7까지 진행되는 회의이다. 앗 그런데 시간 2에는 사용할 수 있는 회의실이 없으므로, 사용중인 회의실이 가장 빨리 끝나는 시간 5까지 기다린다.. 세번째 회의는 3시간이 밀려서 시간 5부터 10까지 이뤄진다.
네번째 회의는 시간3부터 4까지 이뤄져야 하는 회의였지만, 사용할 수 있는 회의실이 없어서 미뤄졌다. 첫번째 회의와 세번째 회의가 모두 시간 10에 끝나므로 네번째 회의는 7시간이 미뤄져서 시간 10부터 11까지 회의가 이뤄진다.
회의실이 둘 다 2번씩 회의가 진행되었으므로, 둘 중 숫자가 작은 회의실인 0번 방이 정답이 된다.
자 이제 각 단계에서 우리가 어떤 것을 알아야 하는지, 어떤 부분을 코드로 옮길 수 있는지 살펴보자.
우선 각 단계에서는 (1) 빈 회의실이 있는지, 있다면 가장 작은 번호의 회의실은 몇번인지 (2) 빈 회의실이 없다면 가장 먼저 회의가 끝나는 시간과 회의실의 번호는 무엇인지 이 두가지를 알아야한다.
그리고 마지막 정답을 말하기 위해서는 (3) 각 회의실마다 회의가 열린 횟수 를 알고 있어야 한다.
(1) 빈 회의실이 있는지, 있다면 가장 작은 번호의 회의실은 몇번인지
빈 회의실의 대한 정보를 저장하는 자료구조가 필요하다. 매번 가장 작은 번호의 회의실이 필요하니 우선순위 큐 형태로 저장할 수 있을 것 같다.
(2) 빈 회의실이 없다면, 가장 먼저 회의가 끝나는 시간과 회의실의 번호는 무엇인지
빈 회의실에 대한 정보와 마찬가지로 진행중인 회의에 대해 저장하고 있는 자료구조도 필요하다. 회의가 끝나는 시간을 기준으로 우선순위 큐를 만들고, 회의실의 방 번호도 같이 저장해주면 될 것 같다.
(3) 각 회의실마다 회의가 열린 횟수
이건 단순하게 생각해서.. 딕셔너리에 방 번호와 회의 횟수를 저장해도 될것이다. 그리고 매 iteration이 돌때마다 지금 내가 회의를 배정해준 이 방이 가장 회의가 많이 열린 방인지 확인해서 저장해주어도 좋을 것 같다.
제출한 코드
나의 경우는 보통 파이썬으로 코딩테스트 연습도 하고, 실제 면접도 진행한다. 이번에도 파이썬으로 알고리즘 문제를 풀었다.
heapq 를 사용할수도 있었지만, 사용하지 않고 한번 풀어보고 싶어서 처음에는 아래와 같이 리스트와 sort를 활용해보았다. 전회사에서는 회사 자체적으로 코딩테스트를 치뤄서 등급을 부여해주는 시스템이 있었는데, 거기에서는 라이브러리 사용이 제한적이여서 간단한 자료구조는 직접 구현해서 문제를 풀어야했다. 그때 습관이 남아있어서, 지금도 최대한 라이브러리 사용하지 않고 문제를 풀어보고 있다. (하지만 heapq는 사용 안하면서 sort()는 사용하는 아이러니..)
class Solution:
def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
available = [i for i in range(n)]
scheduled_endtime = []
scheduled_room = {}
meetingroom = {i: 0 for i in range(n)}
max_room = 0
meetings.sort()
for m in meetings:
scheduled_endtime.sort()
while scheduled_endtime and scheduled_endtime[0] <= m[0]:
endtime = scheduled_endtime.pop(0)
scheduled_room[endtime].sort()
room = scheduled_room[endtime].pop(0)
available.append(room)
available.sort()
end, room = None, None
if available:
room = available.pop(0)
end = m[1]
else:
endtime = scheduled_endtime.pop(0)
scheduled_room[endtime].sort()
room = scheduled_room[endtime].pop(0)
delay = endtime - m[0]
end = m[1] + delay
scheduled_endtime.append(end)
if end not in scheduled_room:
scheduled_room[end] = []
scheduled_room[end].append(room)
meetingroom[room] += 1
cond1 = (meetingroom[max_room] < meetingroom[room])
cond2 = (meetingroom[max_room] == meetingroom[room] and room < max_room)
if cond1 or cond2:
max_room = room
return max_room
heaq를 직접 구현해서 사용해보았다. 완전이진트리를 리스트 형태로 구현하는게 제일 간편해보여서 그렇게 구현해보았다. 하지만 아무래도 python 내장 로직의 효율성을 따라가기엔 좀 역부족이다. 속도가 어째 첫번째것보다 느리다. ㅎㅎㅎ
비어있는 방 목록과 회의가 끝나는 시간 목록을 같은 자료구조로 사용하고 싶어서 구현하다보니 PQueue value[i] = [value1, value2] 이런 형태이다.
class PQueue:
def __init__(self, v):
self.value = v
self.heapify()
def compare(self, a, b):
cond1 = self.value[a][0] < self.value[b][0]
cond2 = self.value[a][0] == self.value[b][0] and self.value[a][1] < self.value[b][1]
if cond1 or cond2:
return True
return False
def push(self, v):
self.value.append(v)
index = len(self.value) - 1
while index > 0:
parent = (index-1)//2
if self.compare(index, parent):
self.value[parent], self.value[index] = self.value[index], self.value[parent]
index = parent
else:
break
def heapify(self):
index = 0
while index < len(self.value):
left, right = (index+1)*2-1, (index+1)*2
cur = index
if left < len(self.value) and self.compare(left, cur):
cur = left
if right < len(self.value) and self.compare(right, cur):
cur = right
if cur == index:
return
self.value[index], self.value[cur] = self.value[cur], self.value[index]
index = cur
def pop(self):
res = None
if self.value:
res = self.value.pop(0)
if len(self.value) > 1:
self.value = self.value[-1:] + self.value[:-1]
self.heapify()
return res
class Solution:
def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
available = PQueue([[i, 0] for i in range(n)])
scheduled = PQueue([])
meetingroom = {i: 0 for i in range(n)}
max_room = 0
meetings.sort(key=lambda x:x[0])
for [start, end] in meetings:
while scheduled.value and scheduled.value[0][0] <= start:
endtime, room = scheduled.pop()
available.push([room, 0])
delay = 0
room = -1
if available.value:
room, _ = available.pop()
else:
endtime, room = scheduled.pop()
delay = endtime - start
scheduled.push([end + delay, room])
meetingroom[room] += 1
cond1 = (meetingroom[max_room] < meetingroom[room])
cond2 = (meetingroom[max_room] == meetingroom[room] and room < max_room)
if cond1 or cond2:
max_room = room
return max_room
라이브 코딩테스트의 경우에는 첫번째 풀이까지만 진행해도 훌륭한듯하고, 면접 전 코딩테스트에서는 두번째 풀이 혹은 파이썬 자체 heapq를 사용해서 문제를 풀면 좋을것 같다는 생각이 들었다.
'Problem Solving' 카테고리의 다른 글
| 70. Climbing Stairs (0) | 2022.11.01 |
|---|---|
| 62. Unique Paths (0) | 2022.10.30 |
