BOJ 1931:会議室-C++の手配


会議室を手配する



コード#コード#


[タイムアウトコード]

#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)入力でベクトルに保存
    2)開始時間を優先順位付け(同じ場合は短い終了時間順で順位付け)
    3)2つのforゲート、最大
  • 結果
    :O(N^2)コードタイムアウト!
    (毎秒約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!
    :会議の終了順に優先順位を付けるのが
  • のコア