강의실 배정 (골드 5)

강의실 배정 성공

 

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

1 초

256 MB

42091

12381

9152

28.947%

문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

출력

강의실의 개수를 출력하라.

예제 입력 1 복사

3
1 3
2 4
3 5

예제 출력 1 복사

2

---

• 접근 방법

 

먼저 기존의 생각대로 로직을 풀기 쉽지 않았던 문제였다.

 

정렬을 하지 않은 채로 생각하면, 강의실을 배정하는 것이 힘들어졌기 때문이다.

 

해당 문제의 키워드 

 

• 우선순위 큐 ( heap)
• 정렬 sort

 

를 이용하여 처음 시작 시간 이후

 

 

다음 강의 시작 시간과 강의가 끝나는 시간을 비교하여

 

1. 강의 시작 시간 보다. 다음 회의 시작 시간이 빠르면 -> 새 강의실 배정

2. 강의 시작 시간 보다  다음 회의 시간 시간이 늦으면 -> 기존 강의실로 배정 후 강의가 끝나는 시간을 새로 업데이트

 

나의 경우는 우선순위 큐 (heap 자료구조)를 사용해 보았지만, 그리디 문제와 같이 사용해 본 적이 없었다.

 

다익스트라 구현 시 에만 활용 하였음으로 힙 자료구조에 대한 활용도가 없었다.

 

그리디의 특성은 2 번 강의가 끝나는 시간을 업데이트하며 로직을 도는 것이었다.

---

• 정답

---

• 정답 로직 - 힙과 정렬을 이용한 로직을 하나하나 분석하였다.

1. 강의 시간 2차원 리스트 저장 (입출력 처리)
2. 오름차순으로 정렬 ([0]번 인덱스 (시작 시간) 기준으로)
3. 우선순위 큐에 처음 강의 끝나는 시간 저장
4. for문을 순회하며 

• heap의 특성으로 가장 빨리 끝나는 강의실과
• 다음 시작 할 강의실을 비교 ( 정렬 된 상태이기 때문에 만약 다음 시작 할 강의시간이 더 빠르면 배정 강의실이 추가되야함)
• ture : 새 강의실을 배정하기 위해 heap에 해당 강의가 끝나는 시각 저장
• false : 기존 강의실을 사용하기 때문에 강의실이 비는 시간 ( 가장 늦게 끝나는 강의가 끝나는 시간) 으로 업데이트 => heappop() 으로 기존 원소 제거 후 -> heappush로 끝나는 시간 저장

 

결과

우선순위 큐 room 리스트에 저장된 시간의 수는 곧 배정된 강의실의 수가 된다.

print(len(room))

 

---

배운 점 및 느낀 점

• 우선순위 큐 사용 방법
• 정렬과 힙을 통한 로직

---