BAEKJOON #1931

 

문제요약

N개의 회의에 대하여 회의 시작시간과 끝나는 시간이 주어진다. 한 개의 회의실에 시간이 겹치지 않게 하면서 사용할 수 있는 회의의 최대 개수를 찾아라.

---

아이디어

그리디 알고리즘 문제니까 최적의 경우를 먼저 골라야한다. 각 회의의 시작 시간과 끝나는 시간이 정렬되지 않은 체 주어진다.

ex) (0,2), (2, 3), (3, 8), (3, 6), (6,9) 가 주어졌다고 가정하자.

(0, 2), (2, 3) 고르고 난 뒤, (3, 8)과 (3, 6)중에 (3, 6)을 골라야 최대이다.

 

현재 회의 끝나는 시간 < 그 다음 회의 시작 시간 =>  회의실 이용 가능

끝나는 시간 기준으로 회의실 이용 가능한지 여부가 판단된다.

입력받은 회의 시간들은 시작 시간 기준으로 오름차순으로 정렬해주지 않는다.

즉, 끝나는 시간을 정렬해서 최대 개수를 구해야 한다.

 

---

코드

N = int(input())

meetings= []
n=0
for i in range(N):
    start, end = map(int, input().split())
    meetings.append([end, start])

meetings.sort() #끝나는 시간을 기준으로 정렬
max_end=0
cnt=0

for meeting in meetings:
    end, start = meeting
    if max_end <= start:
        cnt+=1
        max_end = end
        
print(cnt)