문제접근
•
빨리 끝나는 것들을 찾아서 선택
놓쳤던 부분
•
회의가 끝나는 시간을 기준으로만 정렬을 했었는데, 회의가 끝나는 시간이 같은 경우를 위해서 우선적으로 회의가 시작하는 시간을 기준으로 정렬하고 회의가 끝나는 시간으로 정렬을 해야한다
•
2차원 vector보다 pair를 사용하면 메모리관점과 속도측면에서 유리
코드
2808 KB
28 ms
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
bool cmp(pair<int, int> a, pair<int, int> b)
{
if (a.second == b.second)
return (a.first < b.first);
return (a.second < b.second);
}
int main(void)
{
int n;
vector<pair<int, int> > meeting;
int min;
int answer = 1;
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
cin >> n;
meeting.resize(n);
for (int i = 0; i < n; i++)
{
cin >> meeting[i].first;
cin >> meeting[i].second;
}
sort(meeting.begin(), meeting.end(), cmp);
min = meeting[0].second;
for (int i = 1; i < n; i++)
{
if (meeting[i].first >= min)
{
answer++;
min = meeting[i].second;
}
}
cout << answer;
return (0);
}
C++
복사
