[c++][BOJ][1931] 회의실 배정

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

그리디를 적용시키는 문제입니다.

 

뭐로 그리디를 적용시킬까 고민하다가 종료시간을 기점으로 그리디를 시키면 된다는 것을 알았습니다.

 

종료시간을 기준으로 pair함수를 이용해서 정렬시킵니다.

 

그 이후 빨리 시작하는 것부터 시작을 한 후 종료시간을 저장시킵니다.

 

종료시간 이후로 혹은 같은 시간에 시작하는 것 중 짧은 종료시간을 가진 것을 찾습니다.

 

이런식으로 이어가면서 개수를 카운트하면 끝 !

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int main(){
    int n;
    cin >> n;
    vector<pair<int, int>> arr(n);
        
    for(int i=0; i<n; i++){
        cin >> arr[i].second >> arr[i].first;
    }
    
    sort(arr.begin(), arr.end());
    
    int index = 0;
    int count = 0;
    
    for(int j=0; j<arr.size(); j++)
    {
        if(arr[j].second >= index){
            index = arr[j].first;
            count++;
        }
    }
    cout << count;
}