백준 1931 - 회의실 배정 - 그리디 알고리즘

문제

문제링크 : https://www.acmicpc.net/problem/1931

풀이전략

1. 회의가 겹치지 않도록 할수 있는 회의의 최대 수를 구한다.
2. 잘 생각해보면 모든 회의의 크기는 결국 1개이다. 따라서 회의가 끝나는 시간이 빠른 순으로 나열하여, 순차적으로 회의를 넣어주면 된다.
   먼저 회의 시작 시간이 빠른 순, 이후 회의 끝나는 시간이 빠른 순으로 나열한다.

• 회의가 끝나는 시간이 빠른 순으로 정렬하는것이 이문제의 핵심 아이디어이다.

코드

#include<cstdio>
#include<vector>
#include<utility>
#include<algorithm>

using namespace std;
// pair형은 가만히 sort만 하면 first만 sort하므로, second까지 sort해주기 위한 함수
bool mySort(const pair<int, int> &a, const pair<int, int> &b){
    return (a.second < b.second);
}

int main(){
    int N, min, cnt = 0;

    scanf("%d",&N);
    vector<pair<int, int> > v;
	int ta, tb;
    for(i=0; i<N; i++){
        scanf("%d %d",&ta, &tb);
        v.push_back(make_pair(ta, tb));
    }
	// pair의 first부분을 먼저 정렬한다.
    sort(v.begin(), v.end());
    // 이후 pair의 second 부분을 정렬한다.
    sort(v.begin(), v.end(), mySort);
    
    // 회의 종료시간이 빠른것이 더 중요하므로 pair의 second를 나중에 정렬한 것이다. 

    min = v[0].second;
    cnt++;

    for(int i=1; i<N; i++){
        if(v[i].first >= min){
            min = v[i].second;
            cnt++;
        }
    }

    printf("%d\n",cnt);
    return 0;
}

소감

매우 중요한 아이디어이다. 전형적인 그리디 알고리즘이고, 그리디라는걸 파악하지 못했기에 문제를 좀 해맸었다. 다시한번 잘 복습하자.