[ 나의 실패 풀이 ]
#include <string> #include <vector> #include <iostream> #include <cmath> #include <map> #include <algorithm> #include <deque> #include <sstream> using namespace std; bool compare(pair<int,int> a, pair<int,int> b) { if(a.first == b.first) return a.second < b.second; return a.first < b.first; } int main(){ ios::sync_with_stdio(0); cin.tie(0); int N,ans=1,cnt=1; cin >> N; vector<pair<int,int>> v(N); for(int i=0;i<N;i++) cin >> v[i].first >> v[i].second; sort(v.begin(), v.end(), compare); int time = v[0].second; for(int i=1;i<N;i++) { if(time > v[i].first) { cnt++; }else{ ans=max(ans,cnt); time = v[i].second; cnt=1; } } if(cnt != 1) ans=max(ans,cnt); cout << ans; return 0; }
- 맞다고 생각했던 로직
1) 강의가 끝나는 시간에 따라 정렬한 후 비교하며 해결
--> 강의가 끝나는 시간으로 정렬할 경우 시작 시간이 누락하는 경우 발생/* 반례 4 1 2 1 4 2 6 4 5 */
2) 강의가 시작하는 시간에 따라 정렬한 후 단순 차례 비교만 한 경우
(위 코드)/* 반례 - 시작 시간이 3보다 작은 값들을 모두 지나쳐서 개수만 세면 해당 강의가 끝나는 시간들이 무시된다 4 1 3 2 6 2 10 4 5 */
[ 정답 코드 ]
#include <string> #include <vector> #include <iostream> #include <cmath> #include <map> #include <algorithm> #include <deque> #include <sstream> #include <queue> using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); int N; cin >> N; priority_queue<int,vector<int>,greater<int>> pq; vector<pair<int,int>> v(N); for(int i=0;i<N;i++) cin >> v[i].first >> v[i].second; sort(v.begin(), v.end()); pq.push(v[0].second); for(int i=1;i<N;i++) { if(pq.top() > v[i].first){ pq.push(v[i].second); }else{ pq.pop(); pq.push(v[i].second); } } cout << pq.size(); return 0; }
- key point!
1) 입력을시작 순서
대로 정렬
2) 단순 비교가 아니라 지속적인 영향을 줄 수 있기에 보관해야함
-->priority_queue
사용
(강의 끝시간과 다음 시작시간을 단순비교만 하고 넘어가는것이 아님)
[ 회의실 배정 vs 강의실 배정 ]
- 회의실 배정은 하나의 회의실에 최대한 많은 강의를 할 수 있도록 하는 것
--> 끝시간으로 배열해서 단순 비교
--> 단순 비교라는 것은 영향을 주지 않고 무시되도 되는것!- 강의실 배정은 최소한의 강의실 개수를 찾기 위한 것
(겹치는 강의 개수를 세어아햠)
--> 강의 끝난 시간이 영향을 계속 줄 수 있어서 자료구조로 유지해서 비교해야함