[백준 1931] 회의실 배정
1. 문제 설명
2. 문제 분석
끝나는 시간을 빠른 순서대로 주어진 회의를 정렬해, 지금 끝나는 시점에서 선택 가능한 회의
를 하나씩 골라간다.
- 가장 많은 회의를 고르기 위해서는 끝나는 시간이 빠른 순서대로 회의를 정렬한다. 끝나는 시간이 같다면, 시작하는 시간이 빠른 순서대로 고르자.
- 순서대로 회의를 확인하면서,
지금 택한 회의 종료 시점
을 기준으로 고를 수 있는 회의가 있다면 선택하자.
끝나는 시간을 빠른 순서대로 주어진 회의를 정렬해,
지금 끝나는 시점에서 선택 가능한 회의
를 하나씩 골라간다.
- 가장 많은 회의를 고르기 위해서는 끝나는 시간이 빠른 순서대로 회의를 정렬한다. 끝나는 시간이 같다면, 시작하는 시간이 빠른 순서대로 고르자.
- 순서대로 회의를 확인하면서,
지금 택한 회의 종료 시점
을 기준으로 고를 수 있는 회의가 있다면 선택하자.
이 문제에서 끝나는 시점과 동시에 시작할 수 있기 때문에 end <= new_start
일 때 주어진 회의를 선택할 수 있다.
이 시점에서 회의를 하나 더 할 수 있기 때문에 cnt += 1
, 그리고 다음 회의를 추가할 때 기준으로 삼을 회의 종료 시간은 이 새로운 회의의 new_end
이므로 end = new_end
가 된다.
- 그리디 알고리즘을 풀기 위해서는 문제 풀이 기준에 대한 간단한 원칙을 만들어야 한다는 데 주의하자.
end <= new_start
와 같은 문제에서 제시한 사소한 기준을 체크하자.
3. 나의 풀이
n = int(input())
times = []
for _ in range(n):
start, end = map(int, input().split())
times.append([start, end])
times.sort(key=lambda x:(x[1], x[0]))
# 회의가 빨리 끝나는 순서대로 정렬하자. 끝나는 시간이 같다면 빨리 시작하는 순서대로 고른다.
start, end = -1, -1
cnt = 0
for time in times:
new_start, new_end = time
# 지금 끝난 시점에서 시작 가능한 회의라면 고를 수 있다.
if end <= new_start:
end = new_end
# 회의가 끝나는 기준은 이 새로 택한 회의가 마치는 시간이 된다.
cnt += 1
print(cnt)
Author And Source
이 문제에 관하여([백준 1931] 회의실 배정), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@j_aion/백준-1931-회의실-배정
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
n = int(input())
times = []
for _ in range(n):
start, end = map(int, input().split())
times.append([start, end])
times.sort(key=lambda x:(x[1], x[0]))
# 회의가 빨리 끝나는 순서대로 정렬하자. 끝나는 시간이 같다면 빨리 시작하는 순서대로 고른다.
start, end = -1, -1
cnt = 0
for time in times:
new_start, new_end = time
# 지금 끝난 시점에서 시작 가능한 회의라면 고를 수 있다.
if end <= new_start:
end = new_end
# 회의가 끝나는 기준은 이 새로 택한 회의가 마치는 시간이 된다.
cnt += 1
print(cnt)
Author And Source
이 문제에 관하여([백준 1931] 회의실 배정), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@j_aion/백준-1931-회의실-배정저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)