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

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

 

그리디

매 단계에서 최적의 방법을 선택하는 알고리즘. 탐욕법이라고도 한다

항상 최적해를 찾을 수는 없다. 사용 조건은

-시간/공간적 제약으로 최적해를 구하지 못해 근사해를 구해야 하는 문제

-그리디를 사용해도 항상 최적해를 구할 수 있는 문제

여야 한다.

두번째 경우로는

1) 탐욕 선택 속성: 탐욕적으로 선택하더라도 문제의 최적해가 보장될 때

2) 최적 부분 구조: 부분문제의 최적해가 전체 문제의 최적해로 확장될 수 있을 때가 있다.

 

이 문제는 그리디를 사용할 수 있는 문제다.

가장 빨리 끝나는 회의를 선택하면 다른 회의에 사용할 수 있는 시간이 많아지고,

매번 가장 빨리 끝나는 회의를 선택한다면 남은 회의 시간에 대해 똑같이 가장 빨리 끝나는 회의를 선택할 수 있다. (최적 부분 구조)

 

즉 끝나는 시간이 가장 빠른 것부터 선택하여 회의를 배정하면 된다.

 

전체 코드

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

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

using namespace std;
typedef pair<int,int> ci;

int solution(int n, vector<ci>&arr){
    int cnt = 0;
    int finish = 0;
    for(int i=0;i<n;i++){
        if(arr[i].second < finish){ //끝나는 시간보다 다음회의 시작시간이 빠르면 배정불가
            continue;
        }
        finish = arr[i].first; //회의 배정, 종료시간 갱신
        cnt++;
    }
    return cnt;
}

int main()
{
    int n, a, b;
    cin >> n;
    vector<ci>arr(n);
    for(int i=0;i<n;i++){
        cin >> a >> b;
        arr[i] = make_pair(b, a); //끝나는 시간 기준
    }
    sort(arr.begin(), arr.end()); //끝나는시간이 가장 빠른 것부터 정렬
    int ans = solution(n, arr);
    cout << ans;
    return 0;
}