[BaekJoon] 1931번 : 회의실 배정

• 이 글은 c++로 풀이를 작성하였습니다.

문제

 

예시

 

풀이

• 그리디 알고리즘의 대표적인 문제입니다.
• 가장 많이 회의를 하기 위해서는 회의가 가장 먼저 끝나는 회의순으로 정렬 후 동일 시 먼저 시작하는 경우를 탐색하면 됩니다.

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

bool cmp(pair<int,int>& p1, pair<int,int>& p2){
    if(p1.second == p2.second){
        return p1.first<p2.first;
    }
    return p1.second<p2.second;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    vector<pair<int,int>> vec;
    int num;
    cin>>num;
    
    for(int i=0;i<num;i++){
        int a,b;
        cin>>a>>b;
        vec.push_back({a,b});
    }
    
    sort(vec.begin(), vec.end(), cmp);
    
    int cnt = 1;
    int e = vec[0].second;
    for(int i=1;i<num;i++){
        if(vec[i].first>=e){
            e = vec[i].second;
            cnt++;
        }
    }
    cout<<cnt;
}

• 추가로 궁금한 점이나 수정할 부분 있으면 댓글로 남겨주세요.