[백준] 1931번 - 회의실 배정

1차 시도

T = int(input()) # 회의의 수
start, end, cnt = 0,0,0
for i in range(T):
    A, B = map(int,input().split())
    if (end <= A):
        start = A
        end = B
        cnt += 1
print(cnt)

T개의 회의를 입력받을 때 순서대로 회의가 시작된다고 생각했다.
T개의 회의는 입력 순서대로 시작되는 것이 아니므로 입력받은 회의들을 먼저 오름차순으로 sorting할 필요가 있음
-> 또한, 만약 (1,10), (2,2), (3,5) 이런 회의들이 있을 때 끝나는 시간 기준으로 sorting을 하지 않을 경우, (1,10)이 먼저 회의를 점령하면 나머지 뒤에 회의들은 진행될 수 없다. 따라서 최대로 많은 회의를 진행해야 함으로 끝나는 시간 기준 sorting작업이 필요하다.

2차 시도

T = int(input()) # 회의의 수
start, end, cnt = 0,0,0
lst = []

for i in range(T): # T개의 회의를 입력받고 회의들을 lst에 저장한다.
    A, B = map(int,input().split())
    lst.append([A,B])

lst.sort(key=lambda x : (x[1],x[0])) # 끝나는 시간을 기준으로 오름차순함 정렬한 뒤, 시작하는 시간으로 오름차순 정렬

for i in range(T):
    if (lst[i][0] == lst[i][1]):
        cnt += 1
    elif (end <= lst[i][0]):
        start = lst[i][0]
        end = lst[i][1]
        cnt += 1

print(cnt)

25%정도에서 틀렸습니다가 나온다.
질문에 있는 반례들로 테스트해봐도 잘 나오는데 어떤 부분이 문제인지 잘 모르겠음

lst.sort(key = lambda x: (x[1],x[0]))
-> (x[1], x[0]) 끝나는 시간 기준으로 먼저 sorting 후, 시작하는 시간 기준으로 sorting한다.

최종 코드

T = int(input()) # 회의의 수
start, end, cnt = 0,0,0
lst = []

for i in range(T): # T개의 회의를 입력받고 회의들을 lst에 저장한다.
    A, B = map(int,input().split())
    lst.append([A,B])

lst.sort(key=lambda x : (x[1],x[0])) # 끝나는 시간을 기준으로 오름차순함 정렬한 뒤, 시작하는 시간으로 오름차순 정렬

for i in range(T):
    if (end <= lst[i][0]):
        end = lst[i][1]
        cnt += 1
print(cnt)

굳이 조건을 더 걸어줄 필요가 없었음...끝나는 시간을 기준으로 오름차순 정렬한 뒤, 시작하는 시간을 기준으로 오름차순 정렬하면 무조건 (4,4)와 같이 시작시간과 끝나는 시간이 같은 회의들은 카운팅이 진행된다.

좋은 웹페이지 즐겨찾기