[Algorithm] 회의실 배정문제 BOJ 1931 (feat. Activity Selection Problem, 그리디 알고리즘)

그리디 알고리즘

그리디 알고리즘은 탐욕 알고리즘이라고도 불리며 어떤 순간에 가장 최선의 선택을 하는것을 말한다. 특징은 local하게 최적의 선택을 하는것이 결국 global하게 최적의 해를 도출해준다. 

---

Activity-selection-problem이란?

그리디 알고리즘을 보여주는 한 예시이며 문제는 다음과 같다.

 

한개의 강의실에 n개의 수업들이 있다. 이때 각 수업은 시작시간 끝나는 시간이 주어진다. 

이때, 한개의 강의실에서 수업이 최대 개수가 될 수 있도록 하는 수업 수를 찾으시오.

문제에 대한 예제

이때 문제를 해결하기 위해서는 끝나는 시간을 기준으로 오름차순 정렬한다. 그리고 겹치지 않는 선에서 수업을 선택하여준다. 

 

다음은 위의 문제풀이 방식의 증명이다. 

• 1 < x < y 이면서 수업의 최대 개수 집합이 A = {ax, ay, .....}이라고 하자. (x와 y는 밑의 첨자이다)
• a1은 ax보다 끝나는 시간이 더 빠르기 때문에, A' = {a1, ay, .....} 또한 최대 개수의 집합이다.
• a1을 선택했을 때에도 수업 최대 개수의 집합은 한가지이며 마찬가지로 겹치지 않는 선에서 다른 수업들도 교체 가능하다. 

 

 

---

백준 1931 문제 풀이

문제의 입력으로 회의의 시작시간과 끝나는 시간이 주어진다. 이 문제를 어떻게 하면 최대로 회의를 선택하도록 할 수 있을까?

1. 회의시간이 짧은 순서대로 선택하기

2. 끝나는 시간이 빠른 순서대로 선택하기 

등등이 있을 것이다. 그리디하게 생각해보면 가장 빨리 끝나는 시간을 먼저 선택하면 더 많은 회의를 배정할 수 있을것이다 (2번). 이 문제에서 주의해야할 것은 

5

4 4

4 4

3 4

2 4

1 4

다음과 같은 input이 들어올때 최대로 회의를 배정해야하기 때문에 끝나는 시간이 같다면 시작시간이 빠른 순서대로 정렬을 해주어야한다. 

 

---

코드

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

bool comp(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;
    for(int i = 0; i < n; i ++)
    {
        int a, b;
        scanf("%d %d",&a, &b);
        
        v.push_back(make_pair(a, b));
    }
    
    sort(v.begin(),v.end(), comp);
    
    int start = v[0].first;
    int end = v[0].second;
    int count = 1;
    
    for(int i = 1; i < n; i++)
    {
        int temp_start = v[i].first;
        int temp_end = v[i].second;
        
        if( temp_start >= end )
        {
            end = temp_end;
            count++;
        }
    }
    
    printf("%d\n",count);
    
    
}