[백준] 1931번 : 회의실 배정 (파이썬)

문제

나의 첫번째 답안

n=int(input())
to=[]
last=0
count=0

for i in range(n):
    st,et=map(int,input().split())
    to.append([st,et])

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

for i,j in to:
    if i>last: #***
        count+=1
        last=j
print(count)

회의의 시작시간과 끝나는 시간이 같을 수도 있다는 것을 고려하지 않았다.

나의 답안

import sys
input=sys.stdin.readline

n=int(input())
to=[]
last=0
count=0

for i in range(n):
    st,et=map(int,input().split())
    to.append([st,et])
to.sort(key=lambda to:(to[1],to[0]))

for i,j in to:
    if i>=last:#같다는 것을 고려해야함
        count+=1
        last=j
print(count)

접근방법

• "회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다"
  "회의의 시작시간과 끝나는 시간이 같을 수도 있다"
• 위와같은 조건에 따라, 중복을 허용한다.(ex 시작하는 시간:1, 끝나는 시간: 1) 따라서 시작 시간과 끝나는 시간이 같다는 것을 고려해야 한다.
• 더불어 최대의 경우의 수를 구하기 위해 끝나는 시간으로 정렬을 해야한다. 끝나는 시간이 늦을수록, 회의 개수가 적어지기 때문이다. 이후, 회의 끝나는 것과 동시에 다음 회의가 시작될 수 있으므로, 시작 시간으로 정렬 해야한다.
  
  

0. (선택) 입출력 속도를 향상시키기 위해 input=sys.stdin.readline 를 사용해주었다.
1. to는 각 회의의 시작, 끝 시간을 저장한다. last는 회의의 마지막 시간, count는 회의의 개수를 저장하는 변수이다.
2. 반복문으로 회의 개수(n)만큼의 입력을 받는다.
3. sort를 사용해 정렬, key로 lambda를 사용해 끝나는 시간(to[1])으로 정렬한 후, 시작하는 시간(to[0])으로 정렬한다.
4. 다음 반복문으로 to배열의 시작 시간(i), 끝나는 시간(j)에 접근한다.
   만약 시작시간(i)이 회의의 마지막 시간(last)과 같거나 크면 회의의 개수(count)를 1 증가시키고, 마지막 회의 시간(last)을 끝나는 시간(j)으로 변경한다.