반응형
https://www.acmicpc.net/problem/1931
1931번: 회의실 배정
(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.
www.acmicpc.net
[ 문제풀이 ]
끝나는 시간이 짧은 회의일수록 더 많은 회의에 참여할 수 있고, 끝나는 시간이 짧은 회의 중 시작하는 시간이 가장 빠른 회의를 하나씩 넣어가면서 문제를 풀었습니다.
1. 끝나는 시간이 짧은 회의일수록, 그중 시작하는 시간이 가장 빠른 회의일수록 앞으로 배치되게 정렬합니다.
2. 가장 앞에 있는 회의를 이전 회의의 끝나는 시간과 비교하여 이전 회의의 끝나는 시간보다 회의의 시작시간이 더 늦다면 ans를 1씩 더해줍니다.
3. 방금 시작한 회의의 끝나는 시간을 cur변수에 갱신시켜줍니다.
4. ans를 출력해줍니다.
[ 소스 코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | #include<iostream> #include<algorithm> using namespace std; struct conference { int start; int end; }; bool cmp(conference left, conference right) { //정렬 순서 if (left.end == right.end) return left.start < right.start; //시작 시간이 빠를수록 return left.end < right.end; //끝나는 시간이 빠를수록 } int N; conference arr[100000]; int main() { scanf("%d", &N); for (int i = 0; i < N; i++) { scanf("%d %d", &arr[i].start, &arr[i].end); } sort(arr, arr + N, cmp); int cur = 0; int ans = 0; for (int i = 0; i < N; i++) { if (cur <= arr[i].start) { cur = arr[i].end; ans++; } } printf("%d", ans); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 3176번 - 도로 네트워크 (C++) (0) | 2022.08.22 |
|---|---|
| [ 백준 ] 1780번 - 종이의 개수 (C++) (0) | 2022.08.21 |
| [ 백준 ] 11047번 - 동전 0 (C++) (0) | 2022.08.19 |
| [ 백준 ] 14889번 - 스타트와 링크 (C++) (0) | 2022.08.18 |
| [ 백준 ] 11727번 - 2xn 타일링 2 (C++) (0) | 2022.08.17 |