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

문제: www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

 

문제풀이

 

그리디 알고리즘을 이용하여 문제를 해결했다.

 

pair 벡터에 회의의 시작시간과 끝 시간을 넣고 종료 시간을 기준으로 오름차순 정렬을 하고 회의 종료 시간이 가장 빠른 회의를 선택한다. 이 때 회의의 시작시간이 이 전 회의의 종료시간과 겹친다면 다음으로 종료시간이 빠른 회의를 선택하여 위의 과정을 반복한다. 

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(pair<int, int> p1, pair<int, int> p2){ //종료시간을 기준으로 정렬
    if(p1.second != p2.second){
        return p1.second<p2.second;
    }
    else{
        return p1.first>p2.first; //시작시간이 늦을수록 겹칠 확률이 적다.
    }
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int N;
    cin>>N;

    vector<pair<int, int>> v;
    for(int i=0; i<N; i++){
        int s, e;
        cin>>s>>e;
        v.push_back({s, e}); //시작시간, 종료시간을 함께 저장
    }

    sort(v.begin(), v.end(), compare); //종료시간 기준 오름차순 정렬

    int cnt = 0, time = 0; //회의수, 현재 시각
    for(auto i : v){
        if(time <= i.first){
            cnt++;
            time = i.second; //현재 시각을 회의 종료시간으로 갱신
        }
    }

    cout<<cnt;
    
    return 0;
}

 

 

결과