문제접근
•
강의실의 개수를 여러개로 할 수 있기 때문에 끝나는 시간으로 정렬을 하면 회의실 개수의 최소값을 구할 수 없음
◦
방을 만들 필요 없는 경우에도 만들어버릴수도 있음
•
강의실을 시작시간으로 정렬하고, pq에 끝나는 시간을 넣어 다음 강의실의 시작시간과 비교하면서 강의실이 새로 필요한지를 구함
놓쳤던 부분
•
answer 변수 따로 필요없이 pq.size()로 답을 구할 수 있었음
코드
3320 KB
44 ms
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
using namespace std;
bool cmp(const pair<int, int> &p1, const pair<int, int> &p2)
{
if (p1.first == p2.first)
return (p1.second < p2.second);
return (p1.first < p2.first);
}
int main(void)
{
int n;
vector<pair<int, int> > time;
priority_queue<int, vector<int>, greater<> > pq;
int answer = 1;
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
time.resize(n);
for (int i = 0; i < n; i++)
cin >> time[i].first >> time[i].second;
sort(time.begin(), time.end(), cmp);
pq.push(time[0].second);
for (int i = 1; i < n; i++)
{
if (pq.top() <= time[i].first)
pq.pop();
else
answer++;
pq.push(time[i].second);
}
cout << answer;
return (0);
}
C++
복사
