백준 1931번 - 회의실 배정

출처 : 1931번: 회의실 배정 (acmicpc.net)

1931번: 회의실 배정

---

회의실 배정 성공분류

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율

2 초

128 MB

74661

21956

15906

28.695%

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용 표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

 

---

[ 문제 설명 ]

 

어떤 식으로 시간표에 있는 회의 시간을 줄을 세워야 원하는 조건대로 값이 나올 수 있는지가 관건인 문제이다.

 

우선 이 문제는 회의실을 안 겹치고 최대한 많이 배정할 수 있는 방법에 대한 문제이다. 기본적인 부분을 인지하고 들어가자.

 

그림으로 설명하겠다.

 

그림 1 - 배정 방법 아이디어

그림 2 - 배정 방법 아이디어

그림 3 - 배정 방법 아이디어

---

[ 코드 ]

 

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

# print(Plans)

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

# print(plan)

end, res = 0, 0
for time in plan:
    if time[0] >= end:
        end = time[1]
        res += 1

print(res)

 

아이디어에 따른 구현은 비교적 쉽습니다. 끝 나시 간을 기준을 1순위, 시작하는 시간을 2순위로 sorted를 이용해 정렬 후,

 

받는 시간 구역의 시작 시간이 지난 시간구역 끝 시간보다 크다면 최신화 후 카운트 +1 해주는 방법입니다.

 

---

후기

 

너무 오랜만에 포스팅합니다.

 

코테이 후 좌절하고 공부는 계속했지만

 

복습을 게을리했었지만, 다시 차근차근 시작해보려고

 

합니다.