(C++) - 백준(BOJ) 1931번 : 회의실배정 답

www.acmicpc.net/problem/1931

1931번: 회의실배정

정렬 후 회의가 끝나는 시간이 가장 낮은 회의 순으로 배정하시면 됩니다.

 

풀이방법 

 1. 회의가 끝나는 시간을 기준으로 오름차순 정렬

 2. 회의가 끝나는 시간이 같을경우엔 회의 시작시간을 기준으로 오름차순 정렬

 3. 끝시간이 다음 회의 시작 시간보다 작을 때는 회의를 배정

 4. 배정했던 회의개수 답 출력

 

Code

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
int ans;
vector <pair<int,int>> v(100000);

bool cmp(const pair<int,int> &a, const pair<int,int> &b){
    if(a.second == b.second) return a.first<b.first;
    return a.second < b.second;
}

int main(){
    cin >> n;
    for(int i = 0; i<n; i++) cin >> v[i].first >> v[i].second;
    sort(v.begin(),v.begin() + n,cmp);
    int endTime = -1;
    for(int i = 0; i < n; i++){
        if(endTime>v[i].first) continue;
        else endTime = v[i].second,ans++;
    }
    cout << ans <<'\n';
}