[BOJ] 회의실 배정_1931

• 알고리즘 유형 : 그리디
• 풀이 참고 : 동기
• 문제 링크 : https://www.acmicpc.net/problem/1931

늘 언급하지만 해당 내용은 정확하지 않아 개발 공부에 도움이 되지 않습니다. 

그래서 당연히 귀한 시간 내주시어 지적해 주시면 감사드리겠습니다. 

---

풀이 요약

• 가장 중요한 키는 '회의 종료시점으로 오름차순'으로 정렬하면 어떻게 구현할지 보인다. 
• 그다음 반례를 하나 조심해야 하는데 문제에 답이 있다. 
• '회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.'

---

코드(python)

import sys

# 회의실 한개의 n개의 회의에 대한 사용표
# 회의 최대 개수
n = int(input())

arr = []
for _ in range(n):
    a, b = map(int,input().split())
    arr.append((a, b))

# 끝나는 시간을 오름차순으로 정렬 했기 때문에 앞에 꺼만 보면 된다. 
# 시작 시간을 오름차순으로 으로 정렬하는건 만약, (9,9)와 (8,9)가 있다고 가정하면
# 겹치게 되어 카운팅이 안되는데, 실제로는 1번이 카운팅이 되어야 한다. 
    
arr = sorted(arr, key=lambda x: x[0]) #요건 생각 못했다..
arr = sorted(arr, key=lambda x: (x[1], x[0])) 

count1 = 0
check = 0
for i in range(n):
    if check <= arr[i][0]:
        count1 +=1
        check = arr[i][1]

print(count1)

---

배운 점, 배울 점

아직 문제의 특정 조건을 어떻게 고려 해야 할지 와닿지 않는다. 더 많이 풀어봐야겠다.