문제
N개의 강의가 있다. 우리는 모든 강의의 시작하는 시간과 끝나는 시간을 알고 있다. 이때, 우리는 최대한 적은 수의 강의실을 사용하여 모든 강의가 이루어지게 하고 싶다.
물론, 한 강의실에서는 동시에 2개 이상의 강의를 진행할 수 없고, 한 강의의 종료시간과 다른 강의의 시작시간이 겹치는 것은 상관없다. 필요한 최소 강의실의 수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 강의의 개수 N(1≤N≤100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 번호는 1부터 N까지 붙어 있으며, 입력에서 꼭 순서대로 주어지지 않을 수 있으나 한 번씩만 주어진다. 강의 시작 시간과 강의 종료 시간은 0 이상 10억 이하의 정수이라고 가정한다.
출력
첫째 줄에 필요한 최소 강의실 개수를 출력한다.
풀이
먼저 입력에서 강의번호, 강의 시작 시간, 강의 종료 시간을 입력받는데, 강의 번호는 입력만 받고 이 이후로는 별로 쓸모가 없다. 형식상으로만 일단 입력을 받는다. 그리고 강의 시작 시간과 종료 시간을 vector<pair<int, int>> lectures 배열에 입력을 받는다. 입력을 받고 난 후, sort를 하면 시작시간을 기준으로 오름차순으로 정렬될 것이다.
sort한 벡터배열을 기준으로 우선순위 큐 pq에 할당한다.
근데 진행중인 강의의 종료시간이 새 강의의 시작시간보다 더 크다면 cnt++하고, 그게 아니라면 pq.pop()을 해서 빼낸다.
코드
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
priority_queue<pii, vector<pii>, greater<pii>> pq; //최소 힙(오름차순)
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n, num, cnt = 0;
cin >> n;
vector<pii> lectures(n);
for (int i = 0; i < n; i++) {
cin >> num >> lectures[i].first >> lectures[i].second; //강의번호(=num)은 어차피 필요없음. 그냥 형식상 입력받는다.
}
sort(lectures.begin(), lectures.end()); //시작시간을 기준으로 오름차순으로 정렬
for (int i = 0; i < n; i++) {
if (pq.size() > 0) {
if (pq.top().first > lectures[i].first)
cnt++;
else
pq.pop();
}
else
cnt++;
pii lec;
lec.first = lectures[i].second;
lec.second = lectures[i].first;
pq.push(lec);
}
cout << cnt;
return 0;
}
'Koala - 2기 > B반' 카테고리의 다른 글
KOALA - B반 출석부 (0) | 2021.02.22 |
---|---|
KOALA B반 2.22 미팅 (0) | 2021.02.22 |
BFS&DFS 문제 코드 - 4963, 1012, 16236번 (0) | 2021.02.21 |
[11866번] 요세푸스 문제0 (0) | 2021.02.19 |
[11866번] 요세푸스 문제0 (0) | 2021.02.19 |