[Python/백준] 1931 회의실 배정

라인스위핑 문제 응용이다.
백준에서는 반례찾기가 힘들다. 이번에도 sort 기준을 잡는데서 틀렸는데, 처음에는 회의 끝나는 시간만을 기준으로 sort (key = lambda x: x[1]를 했다가 반례에서 잡혔다.

반례는 이것이다. [9,9],[1,9] 이 반례에서는 끝나는 시간 기준으로 하면 line이 [9,9] 기준으로 잡히는데 그러면 [1,9]가 skip 되버린다. 따라서 동일한 시간에 종료되는 회의라면 [1,9]가 뒤로 올 수 있도록 두 개의 키 (끝나는 점, 시작하는 점) 으로 정렬 해야 한다.

또 이 문제에서는 회의의 시작 시간과 끝나는 시간이 동일한 [9,9] 케이스가 있는데 이것을 처리하기 위해서 line <= a[1] and line <= a[0] 와 같이 line과 동일 선상에 놓고 회의 시작 시간과 끝나는 시간을 모두 비교해서 같더라도 처리할 수 있어야 한다.

n = int(input())

arr = [list(map(int, input().split())) for _ in range(n)]

arr = sorted(arr, key = lambda x: (x[1],x[0]))

line = cnt = 0
for a in arr:
    if line <= a[1] and line <= a[0]:
        line = a[1]
        cnt += 1
    else:
        if line > a[0]:
            continue

print(cnt)