[백준 19598] 최소 회의실 개수

www.acmicpc.net/problem/19598

19598번: 최소 회의실 개수

입력으로는 각 회의별 시작시간과 끝나는 시간이 들어온다

최소한 사용할 수 있는 회의실로 겹치지 않게 끔 빌리는게 우리가 해야할 일이다.

 

그래서 나는 시작시간을 기준으로 sorting 을 하고

하나씩 가져와서 기존에 저장한(시작은 없음) 회의실 vector에서 원소랑 비교를한다

 

첫번 째 예로 들면은 

입력

0 40

15 30

5 10

 

sorting 

0 40

5 10

15 30

---

비교시작

1 /////////

처음으로 들어온 0 40은 비교할 게 없으니까 벡터에 바로저장

 

2 /////////

5 10 에서 시작하는 시간이 0 40 사이에 들어오는지 판단한다.

들어오는 경우 같은시간에 예약할 수 없기 때문에 벡터에 새롭게 저장한다.

 

3 /////////

15 30 에 경우 0 40안에 들어가지만

5 10 안에 15가 들어가지 않기 때문에 이 회의실을 사용할 수 있다 사용의 표시로는

5 10 에서 끝나는 시간을 15 30에서 30으로 업데이트한다

 

벡터안에 

0 40

5 30

이렇게 있다 

원소는 두개 = 최소 회의실의 개수

 

사람들이 의문을 가질 수 있는건 그러면 10~15 에 시작하고 끝나는 회의가 있으면 어떻게 하냐?

그것은 이미 Sorting을 통해 배제시킨 조건이기 때문에 가능하다!

 

 

코드는 다음과 같다.

//최소 회의실 개수
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
 
int main(void)
{
    int N = 0;
    unsigned int srt = 0;
    unsigned int end = 0;
    vector<pair<unsigned int, unsigned int> > vpQue;
    vector<pair<unsigned int, unsigned int> > vpTime;

    cin >> N;

    for(int i = 0; i < N; i++)
    {
        cin >> srt >> end;
        vpQue.push_back(make_pair<int,int>(srt,end));
    }
    
    sort(vpQue.begin(), vpQue.end());

    vector<pair<unsigned int, unsigned int> >::iterator  iter;

    for(iter = vpQue.begin(); iter != vpQue.end(); ++iter)
    {        
        int i = 0;
        for(i = 0; i < vpTime.size(); i++)
        {
            if((*iter).first >= vpTime[i].first && (*iter).first < vpTime[i].second)
                continue;
            else
            {
                vpTime[i].second = (*iter).second;
                break;
            }

        }
        if(i ==  vpTime.size())
            vpTime.push_back(*iter);
    }

    cout << vpTime.size() << endl;

    return 0;
}