[백준] 회의실 배정

문제

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

1931번: 회의실 배정

 

주안점

해당 문제는 완전탐색이나, 동적 프로그래밍을 사용하는 방법도 있을것이다. 

하지만 그리디로도 풀이가 가능하다.

 

 

구조

회의실 사용 시작 시각과 종료 시각을 pair로 받아 정렬 후에 그리디 알고리즘으로 순차적으로 입실 가능할 때마다 입실한다.

 

 

코드

#include<bits/stdc++.h>
using namespace std;

vector<pair<int,int>> v;
int n,t,tt,timee,ret;

int main() {
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>t>>tt;
        v.push_back({tt,t});
    }
    sort(v.begin(), v.end());

    for(pair<int,int> vv : v){
        if(vv.second>=timee){
            timee = vv.first;
            ret++;
        }
    }
    cout<<ret<<"\n";
}