[파이썬 알고리즘 문제풀이] - Section4 / 이분탐색(결정알고리즘) & 그리디 알고리즘 - 5

🎈 회의실 배정(그리디)

한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들
려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하
면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중
단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

▣ 입력설명
첫째 줄에 회의의 수 n(1<=n<=100,000)이 주어진다. 둘째 줄부터 n+1 줄까지 각 회의의 정
보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다.

▣ 출력설명
첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.

▣ 입력예제 1
5
1 4
2 3
3 5
4 6
5 7

▣ 출력예제 1
3

import sys
# sys.stdin = open("input.text", "rt")

N = int(input())
data = []
for i in range(N):
    a, b = map(int, input().split())
    data.append((a,b))

#리스트에 튜플 자료형이 들어오고 그냥 sort()를 하면 튜플의 앞 자료를 기준으로 정렬해! 원하는 기준으로 정렬하려면 람다를 활용해서
data.sort(key = lambda x : (x[1], x[0]))

temp = data[0][1]
cnt = 1
for i in range(1, N):
    if data[i][0] >= temp: #시작시간이 끝시간보다 같거나 클 때 
        cnt += 1
        temp = data[i][1]

print(cnt)

#누구를 기준으로 정렬할 지 생각해야함 !
#그리고 어떤 것과 비교할 지. 이정도를 생각할 수 있어야한다. 

🎃 코멘트
그리디 알고리즘. 현재 가장 좋은 선택을 하도록 선택하면 돼 그리고 그리디를 정렬과 함께라고 생각하기