티스토리 뷰
728x90
https://www.acmicpc.net/problem/11000
11000번: 강의실 배정
첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109)
www.acmicpc.net
C++ 그리디 알고리즘, 우선순위 큐
강의 시간표 (시작시간, 종료시간)이 주어지고 최소한의 강의실을 배정하여 강의실 개수를 출력하는 문제
접근방법
그리디 문제 중에 이런 문제는 처음 봐서 좀 헤맸다. 처음엔 브루트포스인가 싶어서 이중포문으로 돌렸었는데
역시 시간복잡도 때문에 아니었던 것 같다.
우선순위큐 두개를 사용해서 풀이한다.
하나는 모든 강의 시간표가 시작시간의 오름차순으로 정렬되어있다(시작시간이 같을 경우 종료시간 오름차순) : pq
다른 하나는 필요한 강의실을 담고있는데, 종료시간이 이른 순으로 (오름차순) 정렬되어있는 큐이다. : cq
pq에서 하나씩 빼서 cq의 top(배정된 강의실 중 가장 빨리 끝나는 강의실의 종료시간)과 비교한다.
그 강의실에서 수업할 수 있으면(cq.top() <= pq.top().시작시간) 이면
그 강의실에 배정한다. 즉 그 강의실의 종료시간이 갱신된다.
cq는 종료시간 순으로 정렬되는 우선순위큐이기 때문에
cq의 top에는 다시 종료시간이 제일 이른 강의실이 top에 위치한다.
이를 pq에 있던 모든 강의가 배정될 때까지 반복한다.
그리고 cq의 size(배정된 강의실 수)를 출력하면 끝
소스코드
#include <iostream>
#include <queue>
using namespace std;
struct comp{
bool operator()(pair<int,int> a, pair<int, int> b){
if(a.first == b.first){
return a.second > b.second;
}else{
return a.first > b.first;
}
}
};
int main(){
//init & input
int N;
cin >> N;
priority_queue<pair<int, int>, vector<pair<int, int>>, comp> pq;
priority_queue<int, vector<int>, greater<>> cq;
int a,b;
for(int i = 0 ; i < N ; i++){
cin >> a >> b;
pq.push(make_pair(a, b));
}
//process
cq.push(pq.top().second);
pq.pop();
while(!pq.empty()){
if(pq.top().first >= cq.top()){
cq.pop();
cq.push(pq.top().second);
pq.pop();
}else{
cq.push(pq.top().second);
pq.pop();
}
}
//output
cout << cq.size() << "\n";
return 0;
}
728x90
'알고리즘 문제풀이' 카테고리의 다른 글
[백준 2470] 알고리즘 112일차 : 두 용액 (0) | 2021.07.29 |
---|---|
[백준 9251] 알고리즘 111일차 : LCS (0) | 2021.07.28 |
[백준 2559] 알고리즘 109일차 : 수열 (0) | 2021.07.26 |
[백준 11728] 알고리즘 108일차 : 배열 합치기 (0) | 2021.07.23 |
[백준 1406] 알고리즘 107일차 : 에디터 (0) | 2021.07.22 |
250x250
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 토마토
- 우선순위큐
- 최소힙
- 트리
- 백준
- 최단경로
- 최대힙
- 이분탐색
- 수학
- 게임이론
- 투포인터
- c++
- 파이썬
- 웹크롤링
- 백트래킹
- 문자열
- BFS
- 동적계획법
- Stack
- dp
- 알고리즘
- 다이나믹프로그래밍
- 브루트포스
- Swift
- 스택
- 정렬
- dfs
- 그리디알고리즘
- 프로그래머스
- 자바
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함