회의실 배정

코드

[ 시간초과 코드 ]

#include <string>
#include <vector>
#include <iostream>
#include <cmath>
#include <map>
#include <algorithm>
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;
    pair<int,int> p;
    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 MAX=1;
    for(int i=0;i<v.size()-1;i++)
    {
        int tmp=i;
        int cnt = 1;
        for(int j=tmp+1;j<v.size();j++)
        {
            if(v[tmp].second > v[j].first) continue;
            cnt++;
            tmp = j;
        }
        MAX = max(cnt, MAX);
    }
    cout << MAX;
    return 0;
}

• 로직
  1) 입력 그대로 vector에 저장
  2) 시작시간을 우선으로 정렬 (같으면 종료시간이 짧은 순서대로)
  3) 2중 for문으로 순회하면서 최대 경우 구함
• 결과
  : O(N^2) 코드로 시간초과!
  (1초에 대략 1억개의 연산을 하니까 2초라서 2*10^8정도까지 되는데 지금은 10^10임 )

---

[ 정답 코드 ]

#include <string>
#include <vector>
#include <iostream>
#include <cmath>
#include <map>
#include <algorithm>
using namespace std;
// 회의가 끝나는 순서에 따라 정렬!
bool compare(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(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N,ans=1;
    pair<int,int> p;
    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<v.size();i++)
    {
        if(time <= v[i].first)
        {
            ans++;
            time = v[i].second;
        }
    }
    cout << ans;
    return 0;
}

• 로직
  1) 회의가 끝나는 순서로 우선정렬 / 같다면 시작 순서가 작은게 우선권
  2) for문 1번으로 순회하며 최적의 경우를 찾는다
• key point!
  : 회의가 끝나는 순서로 우선 정렬을 하는 것이 핵심