[파이썬] 백준 1931 : 회의실 배정

[파이썬] 백준 1931 : 회의실 배정

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

실버 2

그리디 알고리즘, 정렬

---

접근

회의 시작 시간, 끝나는 시간이 모두 빠르면 빠를수록 가능한 회의의 개수가 많아진다.

예를 들어, 1~4시에 끝나는 회의 다음으로 올 수 있는 것은 4시와 같거나 큰 회의 시간뿐이다.

 

또한, 회의 시간이 가장 먼저 끝나는 회의는 반드시 겹치지 않는 회의에 포함된다. (겹치지 않는 회의의 최대 개수를 구하므로)

회의가 끝나는 시간을 기준으로 오름차순 정렬을 하면 처음 회의를 기준으로 다음 회의의 시작시간이 겹칠 수 있는지 없는지에 대한 여부를 반복문을 한 번만 사용해서라도 판단할 수 있다.

 

 

코드(324ms)

import sys
input = sys.stdin.readline
N = int(input())
lst = []

for _ in range(N):
    s, f = map(int, input().split())
    lst.append((s, f))    # 회의시작시간, 끝나는 시간을 튜플 형태로 리스트에 담는다.
lst.sort(key = lambda x : (x[1], x[0]))    # 회의가 끝나는 시간(1순위), 시작하는 시간으로 정렬한다.
cnt = 1     # 겹치지 않는 회의의 개수 (lst[0]은 반드시 포함된다.)
last_time = lst[0][1]    # 첫번째 회의의 끝나는 시간을 할당한다.

for i in range(1, N):
    if lst[i][0] >= last_time:    
        cnt += 1
        last_time = lst[i][1]    # 조건을 충족하는 경우, 새로운 회의의 끝나는 시간을 재할당한다.

print(cnt)

 

시작시간, 끝나는 시간을 튜플 형태로 받고 lst 리스트에 담는다.

그리고 회의를 끝나는 시간을 1순위, 시작 시간을 2순위로 한 오름차순 정렬을 한다.

만약 입력 값이

2

2, 3

2, 1

이라면

2, 1

2, 3 으로 정렬할 수 있게 된다.

 

무엇을 입력하든, 정렬에 의해 [0] 번째 회의는 반드시 겹치지 않는 회의에 포함된다. (제일 먼저 끝나는 회의이므로)

따라서 그 개수를 세는 cnt변수값을 1로 선언한다.

 

회의가 끝나는 시간을 기준으로 정렬되었으므로, 가장 앞에 정렬된 회의를 기준으로 다음 회의 시작시간이 현재 회의가 끝나는 시간보다 빠르지 않으면 cnt를 하나 올린다.

그리고 last_time값을 갱신해줌으로써 반복문을 처음부터 끝까지 한 번만 돌려도 조건에 맞는 회의 시간만 골라낼 수 있도록 했다.

 

최종적으로 cnt값을 출력하게 되면 회의실을 사용할 수 있는 회의의 최대 개수가 나타날 것이다.