TIL) 1931 회의실 배정
이 포스팅은,
1. 미래의 내가 다시 이 문제를 풀고자 할 때 과거의 내가 어떻게 문제를 해결했었는지 알려주기 위해서
2. 같은 문제를 풀고 있는 사람에게 아이디어를 제공하기 위해서
작성되었습니다.
회의실 배정
백준 1931 회의실 배정 : https://www.acmicpc.net/problem/1931
💡 아이디어
첫 번째 풀이
N = int(input())
def choose_num(i, checked):
if i > schedule[-1][0]:
return checked
min_num = 2**31-1
for leng in range(len(schedule)):
if schedule[leng][0] >= i:
min_num = min(schedule[leng][1], min_num)
checked.append(min_num)
return choose_num(min_num, checked)
schedule = []
for _ in range(N):
start, end = map(int, input().split())
schedule.append([start, end, _])
schedule.sort(key=lambda x: x[0])
checked = []
print(len(choose_num(0, checked)))
위의 코드에는 엣지 케이스가 존재한다😭😭😭
😈 edge case 01
12
1 4
3 5
4 4
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14
😈 edge case 02
2
1 2
2 2
이렇게 시간이 0인 회의가 존재할 경우 무한 루프를 돌게된다.
두 번째 풀이
import sys
input = sys.stdin.readline
N = int(input())
schedule = []
for _ in range(N):
start, end = map(int, input().split())
schedule.append((start, end))
schedule.sort(key=lambda x: (x[1], x[0]))
checked = 0
temp_start, temp_end = 0, 0
for i in range(len(schedule)):
start, end = schedule[i]
if i == 0:
checked += 1
temp_start, temp_end = start, end
else:
if start >= temp_end:
temp_start, temp_end = start, end
checked += 1
print(checked)
세 번째 풀이
# ...생략...
temp_start, temp_end = 0, 0
for start, end in schedule:
if start >= temp_end:
temp_start, temp_end = start, end
checked += 1
print(checked)
Author And Source
이 문제에 관하여(TIL) 1931 회의실 배정), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mongle/TIL-1931-회의실-배정저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)