[백준/c++] 1931번: 회의실 배정

 

 

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

1931번: 회의실 배정

 

그리디 문제의 기본으로 나오는 문제였던 걸로 기억하는데, 

이 문제에서 중요한 것은 바로 "종료 시간"이다.

 

그러므로 종료시간을 기준으로 오름차순 정렬을 한 뒤

만약 다음 스케줄의 시작시간이 현재 스케줄의 종료시간보다 빠르다면 이 스케줄은 건너뛴다.

늦거나 같다면 cnt++ 하고 다음 스케줄의 종료시간을 현재 스케줄 종료시간을 저장하는 time에 넣어준다.

 

 

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

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, cnt=1;
    vector<pair<int, int>> v;
    cin >> n;
    for(int i=0; i<n; i++){
        int s, e;
        cin >> s >> e;
        v.push_back({e, s});
    }
    
    sort(v.begin(), v.end());
    
    int time = v[0].first;
    for(int i=1; i<n; i++){
        if(time <= v[i].second){ //다음 s 시작 시간 >= 현재 s 종료시간
            cnt++;
            time = v[i].first;
        }
    }
    
    cout << cnt << '\n';
    return 0;
}