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

---

풀이

그리디 : 문제 푸는 단계에서 가장 좋은 것을 선택하는 것

보통의 그리디는 대부분 정렬과 동반되어 나온다.

 

회의가 끝나는 시각을 기준으로 정렬을 해야 최대한 회의를 많이 할 수 있다.

빨리 끝나는 것이 중요하기 때문이다.

 

2 3 

1 4

3 5 → 회의 진행 가능

4 6

5 7 → 회의 진행 가능

 

그리고 회의의 끝나는 시간과 다음 회의의 시작 시간을 비교해 보는 것이다.

---

코드 1 

n = int(input())
meeting = []
for i in range(n):
    first, second = map(int,input().split())
    meeting.append((first, second)) # 튜플 형태로 저장

meeting.sort(key = lambda x: (x[1], x[0])) # x[1],x[0] 순으로 정렬
# print 하면 second 기준 오름차순으로 정렬된다.

end = 0 # 회의가 끝나는 시간
cnt = 0 # 회의 수
for s, e in meeting: # 회의 시작시간과 끝나는 시간을 받는다.
    if s >= end: # 첫번째 회의가 시작하는 시간이 회의가 끝나는 시간보다 클 때 
        cnt += 1
        end = e
        
print(cnt)

회의 시간을 튜플로 받음.

회의가 끝나는 시간만 기준으로 정렬하면 된다.

 

코드 2

n = int(input())
s = []
for i in range(n):
    first, second = map(int, input().split())
    s.append([first, second])
s = sorted(s, key=lambda a: a[0])
s = sorted(s, key=lambda a: a[1])

end_time = 0
answer = 0
for i, j in s:
    if i >= end_time:
        answer += 1
        end_time = j
print(answer)

끝나는 시간만 기준으로 정렬하면 된다.