강의실 배정

코드

[ 나의 실패 풀이 ]

#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 강의실 배정 ]

• 회의실 배정은 하나의 회의실에 최대한 많은 강의를 할 수 있도록 하는 것
     --> 끝시간으로 배열해서 단순 비교
        --> 단순 비교라는 것은 영향을 주지 않고 무시되도 되는것!
• 강의실 배정은 최소한의 강의실 개수를 찾기 위한 것
  (겹치는 강의 개수를 세어아햠)
      --> 강의 끝난 시간이 영향을 계속 줄 수 있어서 자료구조로 유지해서 비교해야함