[코드트리 파이썬] 회의실 겹치지 않게 하기

문제

 

 

---

풀이

회의의 추가시간과 종료시간이 주어졌을 때 몇개의 회의를 제거해야 가장 많은 회의를 할 수 있는지 구하는 문제이다.

결론부터 말하자면 가장 빠르게 끝나는 회의순으로 배치하면 해결이 가능하다.

 

가령 회의시간이 위의 표처럼 구성되어 있을 때 빨리 끝나면서 겹치지 않는 회의를 고르면

a, (c,d), f, g 가 된다.

c와 d회의는 하나만 선택하면 된다.

for i in range(n):
    a, b = map(int, input().split())

    room.append([a, b])

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

회의실을 입력받고 정렬하는 코드이다.

회의실의 경우 끝나는 시간을 기준으로 정렬해야하므로 람다식을 이용하여 끝나는 시간을 기준으로 정렬한 뒤 만약 같다면 시작 시간을 기준으로 정렬시켰다.

 

endTime = room[0][1]

정렬을 시켰기 때문에 첫 endTime은 가장 앞에 정렬된 종료시간이 된다.

 

for i in range(1, n):
    startTime = room[i][0]
    if startTime >= endTime:
        endTime = room[i][1]
    else:
        res += 1

print(res)

첫 회의는 배치했기 때문에 반복문을 1부터 시작한다.

만약 회의 시작시간이 이전 회의의 끝 시간보다 뒤에 있다면

endTime을 할당하므로써 배치한다.

만약 아니라면 배치가 불가능하므로 res값을 증가시킨다.

 

반복문이 종료된 후 res값을 출력하면 된다.

 

 

코드

n = int(input())

room = []

for i in range(n):
    a, b = map(int, input().split())

    room.append([a, b])

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

endTime = room[0][1]
res = 0

for i in range(1, n):
    startTime = room[i][0]
    if startTime >= endTime:
        endTime = room[i][1]
    else:
        res += 1

print(res)