[백준 1931] 회의실 배정

🔗알고리즘 문제

그리디를 사용하여 해결한 문제이다. 그리디 문제는 접근만 잘 한다면 코드 자체는 어렵지 않은거 같지만 아직 접근하기가 조금 어려운 것 같다.

문제 분석

회의실 사용시간표가 주어질 때 겹치지 않고 진행될 수 있는 최대 회의의 갯수를 구하는 문제이다.

- 회의는 한번 시작되면 중단될 수 없다.
- 회의가 끝나자마자 다음 회의를 시작할 수 있다.

발상

회의가 끝나는 순으로 정렬된 시간표이다. 해당 시간표에서 겹치지 않고 가장 많은 회의를 진행하려면 진한 초록색으로 표시 된 4개의 회의를 진행할 수 있다.

- 회의는 한번 시작되면 중단될 수 없다.

이 말을 다르게 해석하면 시작 된 회의가 있을 때 해당 회의가 끝나는 시간보다 빠르게 시작하는 회의들은 모두 스킵할 수 있다는 뜻이된다.

알고리즘 설계

1. 시간표의 정보를 입력받는다.
2. 시간표를 회의가 끝나는 순으로 정렬한다.
3. for문을 진행하며 마지막 회의가 끝나는 시각보다 시작시간이 앞에 있는 회의라면 스킵한다. 아니라면 마지막 회의를 갱신한다.

코드

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

using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    int n;
    int cur = 0;
    int answer = 0;

    vector<pair<int, int>> v;

    cin >> n;

    for(int i = 0; i < n; i++){
        int start;
        int end;

        cin >> start >> end;
        v.push_back({ start, end });
    }

    sort(v.begin(), v.end(), [](pair<int, int> a, pair<int, int> b){
        if(a.second == b.second){
            return a.first < b.first;
        } 
        return a.second < b.second; 
    });

    for(int i = 0; i < n; i++){
        if(v[i].first < cur)
            continue;

        cur = v[i].second;
        ++answer;
    }

    cout << answer;
}