백준 알고리즘 1931 (회의실 배정) - python

백준 알고리즘 1931 (회의실 배정) - python

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

1931번: 회의실 배정

 

그리디! 회의실 (시작, 끝) 시간이 주어지는 경우 최대 값 구하기

여기서 잘 생각해야 하는 부분은 "회의의 시작시간과 끝나는 시간이 같을 수도 있다."

이 문장을 "일단 시작을 해야지 그 동시에 끝날 수도 있다." 라는 조건으로 해석했다.

그렇기 때문에, 시작 시간 기준으로 먼저 정렬을 한다.

 

[문제 풀이]

1. 받아온 리스트 times를 시작 시간 기준으로 먼저 정렬

2. 정렬된 times를 한 번 더 종료 시간 기준으로 정렬

3. 회의실이 사용 가능한 지 시작과 끝 시간을 비교하면서

4. 가능하면 끝 시간을 갱신해주고

5. 값을 저장해준다. (여기서 카운트만 해줘도 된다.)

6. result의 길이를 출력해준다.

(예제 입력 1의 result에서는 힌트 (1,4), (5,7), (8,11), (12,14)가 들어있다)

 

import sys
N = int(sys.stdin.readline())
times = [list(map(int, input().split())) for _ in range(N)]
times.sort(key=lambda x: x[0])  # 시작 시간 기준 먼저 정렬
times.sort(key=lambda x: x[1])  # 종료 시간 기준 정렬
end_time = 0
result = []
for start, end in times:
    if start >= end_time:  # 회의실 사용 가능하면
        end_time = end
        result.append((start, end))  # 전체 저장
print(len(result))  # 길이만 출력