Greedy Algorithm + 회의실 배정

Greedy Algorithm

그리디 알고리즘이란 문제의 해를 구하는 데에 있어 매 순간에 최적의 값을 택하는 알고리즘이다.

모든 경우의 수를 전부 체크하지 않기 때문에 이 알고리즘을 통해 최적의 경우를 찾았다고 확신할 수는 없다.

따라서 이 알고리즘을 사용할 때에는 실제로 이 알고리즘이 전체 경우의 수를 고려했을 때에도

최적의 결과를 낼 수 있는지를 꼭 고려해 봐야 한다.

다음은 정올 1370번 문제인 회의실 배정(http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=645&sca=3020)의 풀이를 직접 작성한 것이다.

이 경우, 이전 회의가 끝나지 않으면 다음 회의가 진행될 수 없다는 제약 조건을 이용하여

모든 회의의 종료 시각을 기준으로 오름차순 정렬하고, for문을 이용해 모든 조건을 다 돌면서

다음 회의의 시작 시각이 현재 회의의 종료 시각보다 작은 경우에 값을 저장하고, 나머지는 무시해버리면 된다.

어차피 오름차순으로 정렬되어 있기 때문에 시작 시간이 같은 경우 가장 빨리 끝나는 회의가 가장 앞에 위치한다.

...라는 목적으로 작성한 코드인데, 왜인지 잘 작동하지 않는다.

내 컴퓨터에서는 정상적으로 작동하고 값도 잘 나오는데, 정올에 돌리니 Runtime Error가 나더라...

나중에 확실히 성공하게 되면 수정하도록 하겠다.

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
 
using namespace std;
 
bool mySortASC(pair<int, pair<int, int>> i, pair<int, pair<int, int>> j) {
    return i.second.second < j.second.second;
}
 
int main(int argc, char *argv)
{
    vector<pair<int, pair<int, int>>> meet;
    vector<int> ret;
    int num, startHour, endHour, N;
    int minTime = 2147483647;
 
    cin >> N;
    for (int i = 0; i<N; i++) {
        cin >> num;
        cin >> startHour;
        cin >> endHour;
        meet.push_back(pair <int, pair<int, int>>(num, pair<int, int>(startHour, endHour)));
    }
 
    sort(meet.begin(), meet.end(), mySortASC);
    ret.push_back(meet[0].first);
    endHour = meet[0].second.second;
    for (int i = 1; i < N; i++) {
        if (endHour <= meet[i].second.first) {
            endHour = meet[i].second.second;
            ret.push_back(meet[i].first);
        }
    }
    
    cout << ret.size() << endl;
    for (int i = 0; i < ret.size(); i++) {
        cout << ret[i] << " ";
    }
    cout << endl;
 
    system("pause");
    return 0;
}