[C/C++] 백준 19598번 - 최소 회의실 개수

 

 

<코드>

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

typedef pair<int, int> pii;

int N, s, e, ans, cnt;
vector<pii> v;

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

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> s >> e;
        v.push_back({ s, 1 });
        v.push_back({ e,-1 });
    }

    sort(v.begin(), v.end());


    for (int i = 0; i < v.size(); i++)
    {
        cnt += v[i].second;
        ans = max(ans, cnt);
    }

    cout << ans << '\n';

}

 

풀이 방법

 

변수 cnt의 의미를 현재시간 기준으로 사용하고 있는 회의실의 개수로 정의하겠습니다. 

cnt값의 최댓값이 최소한으로 필요한 회의실의 개수입니다.

그리고 벡터에는 {시작시간, 1}와 {종료시간, -1}으로 넣고 정렬을 하였습니다.

 

입력 예시)

5
5 15
0 40
15 30
5 15
10 20

정렬된 벡터

{0, 1}
{5, 1}
{5, 1}
{10, 1}
{15, -1}
{15, -1}
{15, 1}
{20, -1}
{30, -1}
{40, -1}

 

 

시간이 0일 때 

• 2번 회의 시작
• cnt = cnt + 1
• 결과 : cnt = 1

 

시간이 5일 때

• 1, 4번 회의 시작
• cnt = cnt + 2
• 결과 : cnt = 3

 

시간이 10일 때

• 5번 회의 시작
• cnt = cnt + 1
• 결과 : cnt =4

 

시간이 15일 때

• 1, 4번 회의 종료
• 3번 회의 시작
• cnt = cnt - 2 + 1
• 결과 : cnt = 3

 

 

시간이 20일 때

• 5번 회의 종료
• cnt = cnt - 1
• 결과 : cnt = 2

 

시간이 30일 때

• 3번 회의 종료
• cnt = cnt - 1
• 결과 : cnt = 1

 

시간이 40일 때

2번 회의 종료

cnt = cnt - 1

결과 : cnt = 0

 

 

 

시간이 10일 때 cnt이 4이며 최댓값이므로 정답은 4개이다.

 

 

 

 

www.acmicpc.net/problem/19598

19598번: 최소 회의실 개수

 

 

 

풀이 참고 블로그 - sys09270883.github.io/ps/69/