백준 회의실배정

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

N = int(input())
lst = []
for i in range(N):
    s,e = map(int, input().split())
    diff =e - s
    lst.append((s,e, diff))

slst = sorted(lst, key = lambda x:(x[1], x[0], diff))
cnt  = 0

pstart = slst[0][0]
pend = slst[0][1]

for i in range(1, N):
    if slst[i][0] >= pend:
        # print(slst[i][0],slst[i][1])
        cnt += 1
        pstart = slst[i][0]
        pend = slst[i][1]
print(cnt+1)

끝나는 시간이 같다면 빨리 시작하는 순서대로 정렬이 되어야 한다.

예를 들자면

2

2 2

1 2

의 경우 이 상태로 한다면 (2 2)가 되고 (1 2)는 (2 2)의 끝나는 시간보다 시작시간이 일찍이기 때문에 무시되어 1번의 회의가 진행된다고 나온다. 하지만 정렬을 통해 (1 2)가 먼저 선택되면 (2 2)도 선택이 가능해지기 때문에 가능한 회의는 2번으로 결정된다.

 

 

그렇기 때문에 정렬을 1. 끝나는 시간의 오름차순 2. 시작하는 시간의 오름차순으로 해주어야 한다.