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

[문제]

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

1931번: 회의실 배정

[풀이]

입력받은 회의 시간들을 정렬할 때 시작시간과 종료시간이 같을 수 있어 lambda를 이용해 시작시간으로 정렬해준 뒤, 종료시간으로 한번 더 정렬해준다.

5
3 5
1 4
8 11
4 4
2 2

# 시작시간을 기준으로 정렬했을 경우

[[1, 4], [2, 2], [3, 5], [4, 4], [8, 11]]

# 시작시간 기준 정렬 후 종료시간 기준으로 정렬했을 경우

[[2, 2], [1, 4], [4, 4], [3, 5], [8, 11]]

 

 

가능한 회의 개수를 세는 부분은 고민을 많이 했다..

현재 차례인 회의의 끝나는 시간이 시작하는 시간인 회의를 찾아야 하나?.. 했는데 꽤 복잡해질 것 같았다.

 

구글링 해보니 i, j (회의 시작시간, 종료시간)를 같이 for문에 두어 i가 last보다 큰 경우 cnt를 1 증가시켜준 후 last를 끝나는 시간인 j로 초기화한다. 너무 간단...

 

나는 i, j를 for문에 같이 둘 수 있다는 것도 까먹고 있었다. ㅎㅎ

 

[코드]

import sys

if __name__ == '__main__':
    n = int(sys.stdin.readline())
    conference = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
    conference = sorted(conference, key=lambda x: x[0])
    conference = sorted(conference, key=lambda x: x[1])

    last, cnt = 0, 0
    for i, j in conference:
        if i >= last:
            cnt += 1
            last = j
    print(cnt)