https://www.acmicpc.net/problem/1931
이 문제는 그리디 알고리즘을 활용해야한다.
회의의 시작 시간과 다음 회의의 끝나는 시간을 비교하여 시작 시간이 작거나 같으면 선택 가능한 회의 수를 증가시킨다.
그 다음 순회를 위한 시작 시간을 선택된 회의의 시작 시간으로 변경한다.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N;
int dp[1001];
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
vector<pair<int,int>> v;
int s, e;
for (int i = 0; i < N; i++) {
cin >> s >> e;
v.push_back(make_pair(e,s));
}
sort(v.begin(), v.end());
int time = v[0].first;
int result = 1;
for (int i = 1; i < N; i++) {
if (time <= v[i].second) {
result++;
time = v[i].first;
}
}
cout << result << '\n';
}
'Baekjoon Review' 카테고리의 다른 글
[Silver 3] 11659번 구간 합 구하기 4 (0) | 2023.11.27 |
---|---|
[Silver 4] 11399번 ATM (0) | 2023.11.27 |
[Silver 2] 1927번 최소 힙 (0) | 2023.11.27 |
[Gold 4] 1043번 거짓말 (0) | 2023.11.27 |
[Silver 3] 9461번 파도반 수열 (0) | 2023.11.14 |