티스토리 뷰
https://www.acmicpc.net/problem/11000
11000번: 강의실 배정
첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)
www.acmicpc.net
우선순위 큐 구조체만 잘 구현해주면 되는 문제였다.
https://tose33.tistory.com/456
c++) priority_queue cmp 구조체 정의
https://en.cppreference.com/w/cpp/container/priority_queue std::priority_queue - cppreference.com template< class T, class Container = std::vector , class Compare = std::less > class priority_queue; A priority queue is a container adaptor that provides con
tose33.tistory.com
강의들을 시작 시간 기준 오름차순 정렬한다.
우선순위 큐에 pair<int,int>형을 저장하고, pair.second 기준 min heap 이 되도록 한다.
그러면 그냥 강의 시간을 pair형 우선순위 큐에 저장하고, 큐의 top에 가장 빨리 끝나는 강의가 위치하기 때문에 다음 강의의 시작시간이 큐의 top에 위치한 강의의 끝나는 시간보다 이른시간 이면 강의실을 하나 더 늘리면 된다.
'PS' 카테고리의 다른 글
| 백준 1781. 컵라면 (0) | 2022.12.07 |
|---|---|
| 백준 16637. 괄호 추가하기 (0) | 2022.12.07 |
| 백준 6198. 옥상 정원 꾸미기 (0) | 2022.12.03 |
| 백준 14494. 다이나믹이 뭐예요? (0) | 2022.12.02 |
| 백준 2164. 카드2 (0) | 2022.12.02 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- binary search
- Dijkstra
- Implementation
- greedy
- 재귀
- db
- Spring
- Unity
- Kruskal
- C
- CSS
- 이분탐색
- DP
- floyd warshall
- back tracking
- MVC
- BFS
- recursion
- Stack
- 조합
- C++
- 자료구조
- graph
- dfs
- Tree
- permutation
- Brute Force
- Python
- priority queue
- two pointer
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | ||
| 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| 20 | 21 | 22 | 23 | 24 | 25 | 26 |
| 27 | 28 | 29 | 30 |
글 보관함