<백준> 1931번 회의실 배정

문제

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

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

문제 해결 과정:

- 그리디 알고리즘

- 시작 시간과 끝나는 시간을 pair로 만들어서 벡터에 저장

- 첫번째 방법: 

- stl을 사용하여 정렬

- iter에 벡터 맨 앞에 값을 저장한다.

- iter의 끝나는 시간보다 비교하는 값의 시작 시간이 작으면 반복, 이 반복문에서 나오면 카운트를 하고  iter 에 비교하던 값을 넣는다.   

- iter의 끝나는 시간보다 비교하는 값의 끝나는 시간이 작으면 iter에 비교하는 값을 넣는다.

- 위 과정을 반복

- 92퍼에서 시간 초과 발생... 연산이 너무 많은 듯 하다.

- 두번째 방법:

-stl을 사용하여 정렬을 하는데 정렬을 할때 cmp함수 사용, 끝나는 시간이 같으면 시작 시간이 큰것을 반환

-iter에 벡터의 맨 앞에 값을 저장

-iter에 시작 시간이 전에 저장한 끝나는 시간과 같으면 카운트하고 끝나는 시간을 저장

- 위 과정을 계쏙해서 반복함

- 문제 해결

첫번째 방법

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<utility>
#include<vector>
using namespace std;
 
int main() {
    int N;
    int b;
    int e;
    int cnt = 0;
    vector<pair<int, int>> v;
    scanf_s("%d", &N);
 
    for (int i = 0; i < N; i++) {
        scanf_s("%d %d", &b, &e);
        v.push_back(pair<int, int>(b, e));
    }
    
    vector<pair<int, int>>::iterator iter;
    vector<pair<int, int>>::iterator current;
 
    sort(v.begin(), v.end());
    iter = v.begin();
    current = v.begin();
    current++;
    while (iter != v.end()) {
        while (iter->second > current->first) {
            if (iter->second >= current->second) {
                iter = current;
            }
            current++;
            if (current == v.end()) {
                break;
            }
        }
        cnt++;    
        iter = current;
    }
 
    printf("%d", cnt);
    
    return 0;
}

두번째 방법

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<utility>
#include<vector>
using namespace std;
 
int main() {
    int N;
    int b;
    int e;
    int cnt = 0;
    vector<pair<int, int>> v;
    scanf_s("%d", &N);
 
    for (int i = 0; i < N; i++) {
        scanf_s("%d %d", &b, &e);
        v.push_back(pair<int, int>(b, e));
    }
    
    vector<pair<int, int>>::iterator iter;
    vector<pair<int, int>>::iterator current;
 
    sort(v.begin(), v.end());
    iter = v.begin();
    current = v.begin();
    current++;
    while (iter != v.end()) {
        while (iter->second > current->first) {
            if (iter->second >= current->second) {
                iter = current;
            }
            current++;
            if (current == v.end()) {
                break;
            }
        }
        cnt++;    
        iter = current;
    }
 
    printf("%d", cnt);
    
    return 0;
}