BOJ 1931 회의실배정

문제

https://www.acmicpc.net/problem/1931

주어진 구간들 중 겹치지 않도록 최대한 많이 고르는 문제이다.

 

풀이

그리디 알고리즘은 3개의 단계만 뚫으면 풀린다.

1. 어떻게 해서든지 직관적으로 그리디 알고리즘 세우기

2. 탐욕적 선택 속성 증명 ( Greedy Choice Property)

3. 최적 부분 구조 증명 (Optimal Substructure)

 

일단 이 문제는 끝나는 시간이 빠른 순으로 회의를 선택해 나가야 한다.

 

<Greedy Choice Property>

(귀류법)

끝나는 시간이 젤 빠른 S를 선택하지 않은 최적해가 존재한다 가정하자.

이 최적해의 회의는 M1, M2, ... 으로 구성될 것이다.

이때 당연히 M1은 S보다 끝나는 시간이 느리고, M2는 M1다음에 위치하니, S의 끝나는 시간보다 늦게 시작한다.

따라서 M1대신 S를 넣은 S, M2, M3, ... 도 최적해가 될 수 밖에 없다.

 

<Optimal Substructure>

당연히 회의 하나를 선택했으면 그 다음에도 그 회의와 겹치는 것을 제외한 후에 최적의 선택을 해야 한다.

 

이 문제 구현의 유의사항은 바로 비교 기준이다.

끝나는 것이 빠른 순서로만 정렬해 놓고 선택하면 틀렸습니다를 받게 된다.

왜냐하면 (1, 2) (2, 2) 와 같이 끝이 같은 경우에는 시작이 빠른 것을 선택하는 것이 유리하기 때문이다.

 

시간 복잡도 : $O(NlogN)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define MAXN 100000

struct Meeting
{
    int s, e;
    bool operator < (const Meeting& p) const
    {
        if(e==p.e) return s<p.s;
        return e<p.e;
    }
};

int n;
Meeting arr[MAXN+10];
int ans;

int main()
{
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
    int i;

    scanf("%d", &n);
    for(i=0; i<n; i++) scanf("%d%d", &arr[i].s, &arr[i].e);
    sort(arr, arr+n);

    int last=-1;
    for(i=0; i<n; i++)
    {
        if(last<=arr[i].s)
        {
            last=arr[i].e;
            ans++;
        }
    }

    printf("%d", ans);
    return 0;
}