cpp) 백준 1931: 회의실 배정

Problem

https://www.acmicpc.net/problem/1931
 
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다.
 
 

Solution

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

using namespace std;

/* 
빨리 시작한다고 해서 회의를 많이 할 수 있는 것이 아니다.
회의가 빨리 끝나고, 끝나자마자 다른 회의를 시작할 수 있다면
최대 회의 개수를 얻을 수 있다.
*/

int main(){
    ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
    
    int n, begin, end;
    cin >> n;
    vector<pair<int,int>> v;

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

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

    int cnt = 1; // 회의 최대 개수 (정답)
    int time = v[0].first; // 가장 빨리 종료되는 회의 (end)
    
    for(int i=1;i<n;i++){
        if (time <= v[i].second){
            cnt++;
            time = v[i].first;
        }
    }

    cout << cnt << '\n';

   return 0;
}

 
- 회의가 빨리 끝나야 더 많은 회의를 할 수 있다는 아이디어에서 출발한다.
- 회의 종료 시간을 기준으로 오름차순으로 정렬한다.
- vector<pair<Type, Type>> v: 2개의 각각 지정한 타입의 값으로 저장할 수 있으며 저장한 값은 .first와 .second로 접근이 가능하다. 2개의 연관된 값을 같이 저장할 수 있어 관리가 용이하다. 2개의 정렬 조건으로 정렬하고 싶을 때 사용하기 좋다.

- 그리디 알고리즘: 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘