147. 1931(회의실 배정) - 파이썬

import sys
input = sys.stdin.readline

N = int(input())
timeList = [list(map(int, input().split())) for _ in range(N)]
# 시작시간, 끝시간
timeList2 = []
timeList.sort(key=lambda x: (x[1], x[0]))
for val in timeList:
  timeList2.append(val) 
  
endMin = timeList[0][1]
cnt = 1
del timeList[0]
del timeList2[0]
#처음에 시작과 종료시간이 같은 회의가 들어갈 수 있음
  
for val in timeList:
  if val[0] < endMin:
    timeList2.remove(val)
  else:
    endMin = timeList2[0][1]
    timeList2.remove(val)
    cnt+=1  
  
print(cnt)

문제요약

회의실 시작시간과 끝시간이 주어진다. 잘 조율해서 가장 많은 회의가 진행될 수 있도록 하자.

설명

'가장 많은' 이라는 조건이 주어졌다. 끝나는 시간 기준으로 오름차순으로 정렬하고 가장 적은 시간부터 생각하자.

입력 예제를 백준 입력으로 진행해 보겠다.

 

먼저 끝나는 시간기준으로 정렬을 한다.

다음과 같이 시간이 정렬될 것 이다.

그러면 맨 처음에 있는 1시 시작 4시 끝을 선택한다.

 

끝나는 시간을 기준으로

이미 1시 시작 4시 끝을 선택했기 때문에 3시시작 5시끝, 0시시작 6시 끝은 선택할 수 없다.

그다음 가장 빠르게 끝나는 회의는 5시 시작 7시 끝이다.

그 다음도 마찬가지이다.

끝나는 시간은 7시 이기 때문에 7시 전에 시작하는 회의들은 선택할 수 없다.

그래서 [3,8] , [5,9] , [6,10]은 지우고 8시 시작 11시 시작 회의가 가장 빠르게 끝나기 때문에 선택한다.

위와 같이 끝을 기준으로 시작 시간이 끝 시간보다 작으면 선택하지 않는 방향으로 문제를 풀어보자.

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

끝나는 시간을 기준으로 값을 정렬한다. 만약 끝나는 시간이 같다면, 시작시간을 기준으로 정렬을한다.

시작 시간도 고려해주는 이유는 만약 시작과 끝 시간이 같을 경우를 대비해야 하기 때문이다.

 

for val in timeList:
  timeList2.append(val)

timeList값을 timeList2라는 값에 복사해준다.

만약 둘을 같다로 넣을 경우 주소가 들어가기때문에 하나하나 append를 통해서 넣어주어야한다.

 

endMin = timeList[0][1]
cnt = 1
del timeList[0]
del timeList2[0]

맨 처음 값을 설정해준다.

정렬을 했으므로 맨 앞에 있는 회의시간이 가장 빠르게 끝나는 회의이다.

처음 값은 이제 필요 없으므로 삭제해준다. (삭제하지 않으면 나중에 문제가 생긴다.)

for val in timeList:
  if val[0] < endMin:
    timeList2.remove(val)
  else:
    endMin = timeList2[0][1]
    timeList2.remove(val)
    cnt+=1

timeList에 있는 회의시간을 하나하나 꺼낸다.

위에서 설명한것과 같이 만약 끝나는 시간이 시작시간보다 크면 해당 회의는 진행할 수 없다.

조건에 해당되지 않으면 맨앞에 있는 시간이 다음 회의가 된다 (정렬과 삭제를 통해서 가능한 것)