[C++] 백준 알고리즘 1931 회의실 배정 (그리디)

1931번: 회의실 배정 (acmicpc.net)

1931번: 회의실 배정

탐욕 알고리즘이라고 불리는 그리디 알고리즘이란 무엇일까?

그리디 알고리즘이란, 지금 상황에서의 최선의 선택이 곧 정답이라는 알고리즘이다.

시간적으로 효율적이지만, 매번 그리디로 푼 풀이가 정답이 아닐 수도 있다!!

 

그리디 알고리즘을 사용하려면 현재 최선의 선택이 전체 문제의 정답이어야한다.

O(N) 시간복잡도를 가지고, 백만 이상의 입력도 받을 수 있다. 주로 정렬과 우선순위 큐를 함께 이용한다.

 

그리디임을 확인하기 위해서는 많은 수학적 증명이 필요하다고 한다.

그러므로 보통의 경우, 직관적으로 판단하여 그리디를 사용한다고 한다.

 

이번에 풀이한 문제는 회의실 배정이라는 문제이다.

회의의 끝나는 시간과 시작하는 시간이 주어졌을 때,

한 회의실에서 어떻게 해야 많은 팀이 회의를 할 수 있는지 계산하는 문제이다.

 

1. 제일 먼저 끝나는 회의부터 배치한다.

직관적으로 판단해보자! 제일 먼저 시작하는 회의부터 배치하면?

1시부터 6시까지 회의가 가능할 때 한 팀이 1시부터 6시까지 독점할 수 있다!! 그러면 한 팀밖에 사용이 불가능!!

2. 끝나는 시간이 같으면, 먼저 시작하는 회의부터 배치한다.

이 부분이 은근 헷갈렸다. 만약 제일 늦게 시작하는 회의부터 배치하면?

(시작시간 끝나는시간) 1 4, 4 6, 6 6 이 주어졌을 때, 늦게 시작하는 회의부터 배치하면 1 4 이후에 6 6만 올 수 있고 두 팀만 회의할 수 있다.

먼저 시작하는 회의부터 배치하면 1 4, 4 6, 6 6이 모두 올 수 있으므로 세 팀이 모두 회의 가능하다.

 

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

using namespace std;

// 회의가 빨리 끝나는 순으로 정렬
// 끝나는 시간이 같으면 먼저 시작하는 순으로 정렬
// (늦게 시작하는 순으로 하면 4,6과 6,6이 있을 때 6,6만 배정됨. 빨리 시작하는 순으로 하면 4,6 6,6 모두 배정됨)
bool cmp(pair<int,int> a, pair<int, int> b){
    if(a.second!=b.second)
        return a.second<b.second; // 빨리 끝나는 순으로 정렬
    return a.first<b.first; // 끝나는 시간이 같으면 먼저 시작하는 순으로 정렬
}

int greedy(vector<pair<int, int>> meeting, int n){
    int end = meeting[0].second; //가장 빨리 끝나는 미팅 저장
    int ans=1; // 배정할 수 있는 회의실의 최댓값 저장
    for(int i=1; i<n; i++) {
        if(end <= meeting[i].first){ // 배정된 마지막 회의 이후에 시작하는 회의가 있다면
            end = meeting[i].second;
            ans++; //회의실 갯수 추가
        }
    }
    return ans;
}

int main(){
    int n;
    cin>>n;
    vector<pair<int, int>> meeting;

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

    sort(meeting.begin(), meeting.end(), cmp);
    cout<<greedy(meeting, n)<<'\n';
}