Meeting Rooms
회의 목록을 두 개의 배열로 받습니다. 회의 i는 starts[i]부터 ends[i]까지 진행됩니다. 한 사람이 모든 회의에 참석하려고 하므로, 회의 두 개가 겹쳐서는 안 됩니다. 한 회의가 끝나는 바로 그 시점에 다른 회의가 시작할 수 있습니다. 그 사람이 모든 회의에 참석할 수 있으면 true를 반환하고, 그렇지 않으면 false를 반환하세요.
함수
- startsinteger-array
- 각 회의의 시작 시간
- endsinteger-array
- 각 회의의 종료 시간은 시작 시간과 같은 인덱스에 있습니다
- 반환값boolean
- true(두 회의가 겹치지 않으면), 그렇지 않으면 false
제약 조건
1 ≤ starts.length == ends.length ≤ 50000 ≤ starts[i] < ends[i] ≤ 106- 회의는 정렬되어 있지 않습니다. 두 회의가 동일할 수 있습니다.
예제
- 입력
- starts = [9, 13, 10]ends = [10, 15, 12]
- 출력
- true
- 설명
- 시간순으로 회의는 9시부터 10시까지, 10시부터 12시까지, 13시부터 15시까지 진행됩니다. 두 번째 회의는 첫 번째 회의가 끝나는 순간 시작하며, 이는 허용되므로 답은
true입니다.
- 입력
- starts = [1, 4, 7]ends = [5, 6, 8]
- 출력
- false
- 설명
- 1시부터 5시까지의 회의는 4시에 아직 진행 중이고, 4시부터 6시까지의 회의가 시작하므로 답은
false입니다.
제출 시 숨은 테스트 +15개
후속 질문
회의를 한 번에 하나씩 예약한다면, 모든 항목을 다시 정렬하지 않고 어떻게 새 예약을 일정과 O(log n)으로 확인할 수 있을까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
시간이 겹치는 두 회의는 일정 시간 동안 겹쳐야 합니다. 이웃한 회의 사이에 겹치는 시간이 나타나도록 회의를 어떤 순서로 나열할 수 있을까요?
회의를 시작 시간순으로 정렬하세요. 그러면 각 회의는 바로 앞 회의와만 겹칠 수 있습니다. 앞 회의가 끝난 후에 시작한다면 그보다 앞선 모든 회의가 끝난 후에 시작하는 것이기도 합니다.
각 시작 시간을 해당 종료 시간과 짝지은 채 회의를 시작 시간 순으로 정렬하세요. 정렬된 목록을 순회하면서 각 시작 시간을 이전 회의의 종료 시간과 비교하세요. 시작 시간이 더 작으면 충돌하고, 그 종료 시간과 같으면 괜찮습니다.
풀이
모든 회의 쌍을 확인하면 충돌을 찾을 수 있지만, O(n²)의 비용이 듭니다. 시작 시간순으로 정렬하면 확인해야 할 대상이 달라집니다. 각 회의는 정렬된 순서에서 이웃한 회의와만 충돌할 수 있으므로, 회의마다 한 번씩만 비교하면 충분합니다.
모든 쌍을 비교하기
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
각 회의가 다른 회의가 끝나기 전에 시작하면 두 회의는 충돌합니다. 1부터 5까지의 회의와 4부터 6까지의 회의에서는 1은 6보다 앞서고 4는 5보다 앞서므로 충돌합니다. 9부터 10까지의 회의와 10부터 12까지의 회의에서는 10은 10보다 앞서지 않으므로 두 회의는 맞닿기만 합니다.
양쪽에 엄격한 <를 사용하는 덕분에 한 회의가 다른 회의가 끝나는 시점에 정확히 시작할 수 있습니다. 모든 쌍을 검사하고 처음 충돌이 발견되면 false를 반환하세요.
문제는 쌍의 개수입니다. 회의가 n = 5000개이면 쌍은 약 1,250만 개이고, 충돌이 없는 일정에서는 모든 쌍을 확인해야 하므로 가장 큰 테스트에서는 너무 느립니다.
알고리즘
- 모든 인덱스
i와 그 뒤에 오는 모든 인덱스j에 대해: starts[i] < ends[j]이고starts[j] < ends[i]이면 두 회의가 겹칩니다.false를 반환합니다.- 겹치는 쌍이 없으면
true를 반환합니다.
def canAttendMeetings(starts, ends):
n = len(starts)
for i in range(n):
for j in range(i + 1, n):
# two meetings clash when each one starts before the other ends
if starts[i] < ends[j] and starts[j] < ends[i]:
return False
return True시작 시간을 기준으로 정렬하고 인접 항목을 확인하세요
핵심 아이디어
회의를 시작 시간순으로 정렬하되, 각 시작 시간과 해당 회의의 종료 시간을 함께 유지하세요. 이제 아무 회의나 골라 그 바로 앞 회의와 비교해 보세요. 앞 회의가 뒤 회의의 시작 시간보다 늦게 끝나면 두 회의가 겹칩니다. 그렇지 않다면 뒤 회의는 앞 회의가 끝나는 시각과 같거나 그 이후에 시작합니다.
왜 바로 앞 회의만 확인하면 될까요? 지금까지의 모든 회의가 바로 앞 회의의 종료 시각과 같거나 그 이후에 시작한다면, 지금까지의 회의는 서로 겹치지 않으며 바로 앞 회의가 가장 늦게 끝나는 회의입니다. 종료 시각과 같거나 그 이후에 시작하는 새 회의는 모든 회의의 종료 시각과 같거나 그 이후에 시작합니다.
첫 번째 예시에서 정렬된 회의는 9시부터 10시, 10시부터 12시, 13시부터 15시입니다. 시작 시각 10시는 종료 시각 10시보다 이르지 않고, 시작 시각 13시는 종료 시각 12시보다 이르지 않으므로 겹치는 회의가 없습니다. 모든 회의는 최소 1단위 시간 동안 진행되므로 시작 시각이 같으면 항상 겹치며, 이 검사로도 이를 확인할 수 있습니다.
정렬에는 O(n log n)이 걸리고, 순회에는 O(n)이 걸립니다. 회의를 함께 묶어 복사하는 데는 O(n)의 공간이 필요합니다.
알고리즘
- 각 시작 시간을 해당 종료 시간과 짝지으세요.
- 시작 시간을 기준으로 짝을 정렬하세요.
- 첫 번째 회의 이후의 각 회의에 대해 시작 시간을 이전 회의의 종료 시간과 비교하세요.
- 시작 시간이 더 작으면
false를 반환하세요. - 반복문이 끝난 후
true를 반환하세요.
def canAttendMeetings(starts, ends):
meetings = sorted(zip(starts, ends)) # by start time
for i in range(1, len(meetings)):
# a meeting must not start before the one right before it ends
if meetings[i][0] < meetings[i - 1][1]:
return False
return True
함정과 경계 사례
흔히 발생하는 버그는 어느 끝점을 비교하는지, 그리고 맞닿아 있는 회의를 어떻게 처리하는지와 관련이 있습니다.
starts를 정렬하고ends는 입력 순서대로 두는 경우입니다. 각 끝점은 자신의 시작점과 함께 이동해야 합니다. 그렇지 않으면 어떤 시작점을 다른 회의의 끝점과 비교하게 됩니다.<대신≤를 사용하는 경우입니다. 9시부터 10시까지의 회의와 10시부터 12시까지의 회의는 맞닿아 있지만 겹치지는 않으며, 이 경우의 답은true입니다.- 입력 순서에서 각 회의가 다음 회의가 시작하기 전에 끝나는지만 확인하는 경우입니다. 입력은 정렬되어 있지 않으므로 입력에서 이웃한 항목은 아무것도 알려 주지 않습니다.
starts[j] < ends[i]처럼 조건 하나로 쌍을 검사하는 경우입니다. 이 조건은 회의j가 나중에 시작할 때만 유효합니다. 순서대로 5시부터 6시까지의 회의와 0시부터 1시까지의 회의가 있으면,0 < 6은 실제로는 충돌이 없는데도 충돌이 있다고 판단합니다.
자주 묻는 질문4
Meeting Rooms의 시간 복잡도는 얼마인가요?
회의를 시작 시간순으로 정렬하는 데 O(n log n)이 들고, 이웃한 회의끼리 비교하며 훑는 데 O(n)이 드므로 전체 시간 복잡도는 O(n log n)입니다. 모든 쌍을 비교하면 대신 O(n²)이 듭니다.
각 회의를 바로 앞 회의와 비교하는 것으로 충분한 이유는 무엇인가요?
시작 시간을 기준으로 정렬한 후 지금까지 겹치는 일정이 발견되지 않았다면, 지금까지의 회의는 각 회의가 이전 회의가 끝나는 시각 또는 그 이후에 시작되는 연쇄를 이룹니다. 연쇄의 마지막 회의가 가장 늦게 끝납니다. 그 회의가 끝나는 시각 또는 그 이후에 시작하는 새 회의는 이전 회의와 겹칠 수 없습니다.
맞닿는 회의도 겹치는 것으로 간주하나요?
이 문제에서는 그렇지 않습니다. 회의는 다른 회의가 끝나는 정확한 순간에 시작할 수 있습니다. 그래서 검사는 엄격한 start < previous end입니다. 회의가 맞닿는 것이 허용되지 않는다면 검사는 start ≤ previous end가 됩니다.
최소 회의실 수는 어떻게 구하나요?
시작 시간과 종료 시간을 별도의 두 목록으로 정렬한 다음, 두 목록을 함께 살펴보세요. 각 시작 시간마다 방 하나를 열고, 다음 시작 시간 이전이나 같은 시점에 오는 종료 시간마다 방 하나를 비우면 됩니다. 한 번에 열려 있는 방의 최대 개수가 답입니다. 여기서 예 또는 아니요로 답하는 질문은 방 하나로 충분한지 묻는 것과 같습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def canAttendMeetings(starts, ends):
# 여기에 코드를 작성하세요케이스 1
케이스 2
입력
starts = [9, 13, 10] ends = [10, 15, 12]
기대값
true