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

백준 1931 : 회의실 배정

 

문제 링크:

www.acmicpc.net/problem/1931

1931번: 회의실배정

 

 

문제 내용:

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

 

 

Idea:

이 문제는 그리디 알고리즘(Greedy Algorithm)의 대표적인 문제 중 하나이다.

 

그리디 알고리즘이란 지역(local)적인 시각에서 가장 최선을 선택하는 것인데, 이 문제의 포인트는 종료시간이 가장 빠른 회의를 먼저 선택하는 것이다.

 

이 문제에 대한 알고리즘은 다음과 같다.

1. 종료시간이 빠른 순서로 정렬한다.
2. 종료시간이 가장 빠른 회의를 선택한다.
3. 선택한 회의의 종료시간보다 빠른 시작시간을 가지는 회의들은 모두 제거한다.
4. 2~3번을 반복한다.

 

 

Code:

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
 
//끝나는 시간을 기준으로 정렬
//끝나는 시간이 같다면 시작시간이 빠른 순서로 정렬
bool compare(pair<int, int>a, pair<int, int>b) {
    if (a.second == b.second)
        return a.first < b.first;
    else return a.second < b.second;
}
 
int main() {
    int N;
    scanf("%d", &N);
 
    //회의 시작,종료 시간 넣기
    vector<pair<int, int>> v;
    int start, end;
    while (N--) {
        scanf("%d %d", &start, &end);
        v.push_back(make_pair(start, end));
    }
 
    //정렬
    sort(v.begin(), v.end(), compare);
 
    //최대 회의 개수 구하기
    int cnt = 1;
    end = v[0].second;
    for (int i = 1; i < v.size(); i++) {
        if (v[i].first >= end) {
            end = v[i].second;
            cnt++;
        }
    }
 
    printf("%d\n", cnt);
 
    return 0;
}