문제 링크 : https://www.acmicpc.net/problem/1931
요약
한개의 회의실이 있다. N개의 회의의 시작시간과 끝 시간이 주어져 있을 때, 회의가 겹치지 않게 회의실을 사용할 수 있는 회의의 최대 개수를 구하는 문제.
풀이
예제 값을 한번 그림으로 나타내보았다.
시작점을 기준으로 정렬해준다.
맨 앞에 막대(회의시간)를 현재 값으로 두고 순서대로 탐색하면서 현재의 막대의 끝점과 같은 시작점이 나오면 카운트해준다. 탐색 중에 현재 막대의 끝점보다 더 빠른 끝점을 가진 막대가 나오면 현재 막대로 그것을 바꿔준다. 끝까지 탐색이 끝나면 카운트한 값을 출력해준다.
코드
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<pair<int, int>>q;
pair<int, int>now;
int n,s,e,cnt=1;
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> s >> e;
q.push_back({ s,e });
}
sort(q.begin(), q.end());
now = q[0];
for (int i = 1; i < q.size(); i++) {
if (now.second > q[i].second)
now = q[i];
else if (now.second <= q[i].first) {
now = q[i];
cnt++;
}
}
cout << cnt << "\n";
}
'BOJ' 카테고리의 다른 글
BOJ 2212 센서 (0) | 2022.03.10 |
---|---|
BOJ 11000 강의실 배정 (0) | 2022.03.10 |
BOJ 17509 And the Winner Is... Ourselves! (0) | 2022.03.10 |
BOJ 1449 수리공 항승 (0) | 2022.03.10 |
BOJ 4796 캠핑 (0) | 2022.03.10 |
댓글