미소를뿌리는감자의 코딩
[백준 2024/09/30] 1931번 회의실 배정 본문
728x90
1. 문제
https://www.acmicpc.net/problem/1931
2. 접근 방법
문제 풀이는 생각보다 간단하다. 종료 시간을 기준으로 정렬하면 된다.
이후, for 문을 돌면서, 현재 선택된 강의의 종료시간 보다, 시간 시간이 늦는 강의를 고르게 된다면,
가장 빨리 강의가 끝나는 강의를 고르게 될 것이다.
여기서 lambda x: (x[1], x[0]) 에서 x[0] 은 왜 sorting을 해주는 지에 의문이 들었다.
시작 시간은 상관이 없는 것 아닌가?
끝나는 시간이 같다면, 2-5이든 3-5이든 같다고 생각했다.
따라서, 질문 게시판에서 반례를 찾아보다 아래 반례를 찾았다.
https://www.acmicpc.net/board/view/148737
"회의의 시작기간과 끝나는 시간이 같을 수 있다"
이는
2
2 2
1 2
의 예제도 가능함을 의미한다.
만약, 2 2가 선택이 먼저 된다면, 1 2는 선택될 기회를 잃게 된다.
반면 1, 2가 먼저 선택된다면, 2 2는 다음으로 선택될 수 있어 총 2개의 회의를 열 수 있다.
3. 코드
def get_max_meetings(times):
times.sort(key=lambda x:(x[1], x[0]))
cnt = 0
cur_end_time = 0
for s, e in times:
if cur_end_time <= s:
cnt += 1
cur_end_time = e
return cnt
if __name__ == "__main__":
n = int(input())
times = []
for _ in range(n):
s, e = map(int, input().split())
times.append([s, e])
print(get_max_meetings(times))
728x90
'코딩 테스트 > 백준' 카테고리의 다른 글
[백준 2024/10/02] 2098번 외판원 순회 (0) | 2024.10.03 |
---|---|
[백준 2024/10/01] 11049번 행렬 곱셈 순서 (1) | 2024.10.01 |
[백준 2024/09/28] 9084번 동전 (0) | 2024.09.28 |
[백준 2024/09/28] 9251번 LCS (0) | 2024.09.28 |
[백준 2024/09/28] 1904번 01타일 (1) | 2024.09.28 |