会議室を手配する

コード#コード#

[タイムアウトコード]

#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;
}

[正解コード]

#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;
}