[백준/1931/파이썬] 회의실 - Greedy

---

소스코드

N = int(input())

answer = 0

room = []

endTime = 0

for _ in range (N):

  room.append(list(map(int,input().split())))

room.sort(key = lambda x : (x[1],x[0]))

for i in room:

  if endTime <= i[0]:

    endTime = i[1]

    answer += 1

print(answer)

---

알고리즘

끝나는 시간 기준을 1차 정렬을 하고 시작 시간을 기준으로 2차 정렬을 한다.

이 생각을 하게 된 근거는 

"끝나는 시간이 같다면 무조건 짧게 이용하는 순간을 넣어야 한다."

그렇게 된다면 

[[1, 4], [3, 5], [0, 6], [5, 7], [3, 8], [5, 9], [6, 10], [8, 11], [8, 12], [2, 13], [12, 14]]

으로 정렬이 된다.

예제에서는 끝나는 시간이 같은게 없지만 만약 같은게 있었다면

[4,8] 이 있었다고 생각해보자

그러면 [3,8] ,[4,8], [5,9] 이렇게 배열이 되고 endTime = 8이 되고 [4,8]은 자연히 우선순위에서 밀리게 되는 것이다.

그리디 문제였다.