[Greedy] 1931번 회의실 배정

1931번 회의실 배정

 

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

 

문제

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

 

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

 

출력

첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.

 

예제 입력

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

 

예제 출력

4

 

해결방법

Greedy Algorithm 유형의 문제이다

 

 

⭐️ 솔루션 ⭐️

종료 시간을 기준으로 정렬을 한 뒤, 회의실을 배정하면 항상 최적해를 가지기 때문에 그리디 알고리즘으로 문제를 해결할 수 있다

 

먼저 회의실을 배정하는 기준을 여러가지 생각해볼 수 있다

1. 회의 시간이 빠른 순서대로 회의실 배정
2. 회의 시간이 짧은 순서대로 회의실 배정

 

이 두가지 경우는 반례가 존재한다

// 1번 반례
◻︎◼︎◼︎◼︎◼︎◼︎◼︎◼︎◼︎◼︎◼︎◼︎◻︎
◻︎◻︎◼︎◼︎◼︎◻︎◻︎◻︎◼︎◼︎◼︎◻︎◻︎

// 2번 반례
◻︎◼︎◼︎◼︎◼︎◼︎◻︎◼︎◼︎◼︎◼︎◼︎◻︎
◻︎◻︎◻︎◻︎◻︎◼︎◼︎◼︎◻︎◻︎◻︎◻︎◻︎

 

따라서 새로운 기준이 필요하다

회의의 종료시간을 기준으로 회의실을 배정한다면 항상 최대 개수의 회의실을 배정할 수 있다!

구조체를 사용하여 sort() 를 사용하는 법이 미숙하여 구글링으로 방법을 찾았다

 

 

 

소스코드

#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;

struct Time {
    int s,e;
    
    Time() { }
    Time(int _s,int _e) : s(_s),e(_e) { }
};

bool cmp(const Time &t1, const Time &t2){
    if(t1.e == t2.e){
        return t1.s < t2.s;
    }else{
        return t1.e < t2.e;
    }
}

int n,s,e,ans,eTime;
vector<Time> v;

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> s >> e;
        v.push_back(Time(s,e));
    }
    
    sort(v.begin(),v.end(),cmp);
    
    ans = 0;
    eTime = -1;
    for(int i=0; i<v.size(); i++){
        if(v[i].s >= eTime){
            ans++;
            eTime = v[i].e;
        }
    }
    
    cout << ans << "\n";
    
    return 0;
}