BOJ 1931 회의실 배정

URL

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

태그

그리디 알고리즘

정렬

문제 설명

•

NNN개의 회의에 대한 정보가 주어질 때, 사용할 수 있는 회의의 최대 개수를 구하는 문제

◦

회의에 대한 정보는 (시작 시간, 끝나는 시간) 형태로 주어짐.

◦

한 회의가 끝나는 것과 동시에 다음 회의가 시작 가능

예제 입력/출력

•

입력1

Plain Text
복사

•

출력1

Plain Text
복사

제약 조건

•

1≤N≤100,0001 ≤ N ≤ 100,0001≤N≤100,000

•

회의에 대한 정보

◦

0≤0 ≤0≤ 시작 시간 ≤231−1≤ 2^{31} - 1≤231−1

◦

0≤0 ≤0≤ 끝나는 시간 ≤231−1≤ 2^{31}-1≤231−1

문제 풀이

풀이1 브루트 포스 - O(2N⋅N)O(2^{N} \cdot N)O(2N⋅N)

풀이2 그리디 - O(N⋅logN)O(N \cdot logN)O(N⋅logN)

풀이 코드

•

그리디 풀이

N = int(input())
schedules = [tuple(map(int, input().split())) for _ in range(N)]

sorted_schedules = sorted(schedules, key = lambda x : (x[1], x[0]))

ans = 0
lt = 0

for st, et in sorted_schedules:
	if st >= lt:
		lt = et
		ans += 1

print(ans)
Python
복사