반응형
<코드>
#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개이다.
풀이 참고 블로그 - sys09270883.github.io/ps/69/
반응형
'🧩PS > 🥈Nomal' 카테고리의 다른 글
[C/C++] 백준 18870번 - 좌표 압축 (0) | 2021.07.24 |
---|---|
[C/C++] 백준 2581번 - 소수 (에라토스테네스의 체) (0) | 2021.06.07 |
[C/C++] 백준 5525번 - IOIOI (0) | 2021.04.06 |
[C/C++] 백준 4358번 - 생태학 (0) | 2021.04.06 |
[C/C++] 백준 7785번 - 회사에 있는 사람 (0) | 2021.04.06 |