알고리즘/백준
[백준] 1374번 : 강의실
bigkwangs
2024. 2. 16. 23:11
728x90
1374번: 강의실
첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의
www.acmicpc.net
🤔 문제분석
정렬한 데이터를 우선순위큐를 이용하여 문제를 해결하였다. 정렬은 시작위치, 끝나는위치 순서대로 오름차순으로 정렬하였고, 배열을 순회하면서 우선순위큐를 활용하여 강의실 개수를 구한다.
우선순위큐에는 끝나는시간을 넣는다. 끝나는 시간을 넣게되면 다음 시작시간과 끝나는시간을 비교한다.
- 시작시간 ≥ 끝나는시간 : 강의실을 이어서 사용 할 수 있음
- 시작시간 < 끝나는시간 : 강의실을 이어서 사용 불가능 함
💻 코드
import sys
import heapq
input = sys.stdin.readline
N = int(input())
rooms = []
for _ in range(N):
idx, start, end = map(int, input().split())
rooms.append((start, end))
rooms.sort(key=lambda x:(x[0], x[1]))
queue = []
for start, end in rooms:
if queue and start >= queue[0]:
heapq.heappop(queue)
heapq.heappush(queue, end)
print(len(queue))🎯 피드백 및 개선사항
예전에 비슷한 문제를 풀어보아서 문제를 쉽게 해결 할 수 있었습니다.
728x90