백준 1931번 (회의실 배정, C++, priority_queue) / 추가 반례 [BAEKJOON]
문제
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 144010 | 45043 | 31834 | 29.573% |
한 개의 회의 실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용 표를 만들려고 한다. 각 회의 I에 대해 시작 시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의 실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작 시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.
예제 입력 1
11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14예제 출력 1
4힌트
(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.
알고리즘 분류
출처
추가 예제
예제 입력 A
5
6 7
6 6
5 6
5 5
7 7예제 출력 A
5예제 입력 B
5
5 5
5 6
6 6
6 7
7 7예제 출력 B
5예제 입력 C
3
1 1
1 1
0 1예제 출력 C
3예제 입력 D
2
1 4
3 3예제 출력 D
1예제 입력 E
15
1 4
7 7
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
7 7
7 7
7 7
2 13
12 14예제 출력 E
8한 개의 회의실 N개의 회의 회의는 시작 시간과 끝나는 시간이 주어짐 회의 실을 사용할 수 있는 회의의 최대 개수를 구하는 문제
회의는 한번 시작하면 중간에 중단될 수 없음 한 회의가 끝나는 것과 동시에 다음 회의가 시작 회의의 시작 시간과 끝나는 시간이 같을 수 있음 (시작과 동시에 끝남)
회의가 끝나는 시간을 기준으로 가장 낮은 회의를 선택하고 선택한 회의의 끝나는 시간보다 일찍 시작하는 회의를 리스트에서 제외하면 될 것 같다. 자료 구조는 priority_queue 를 사용하면 될 것 같다. 범위도 (2^31) -1이라서 int 내에서 해결 가능
데이터 확인
11
5 9
6 10
3 5
0 6
5 7
8 11
8 12
2 13
1 4
3 8
12 14#include <iostream>
#include <queue>
using namespace std;
priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> myQueue;
int result = 0;
int startLecture = 0;
int endLecture = 0;
void Initializtion()
{
cin >> result;
int N = result;
while (N > 0)
{
cin >> startLecture >> endLecture;
// 강의가 끝나는 시간을 낮은 값으로 정렬
myQueue.push(make_pair(endLecture, startLecture));
N--;
}
}
int main()
{
Initializtion();
while (!myQueue.empty())
{
endLecture = myQueue.top().first;
startLecture = myQueue.top().second;
myQueue.pop();
cout << " LectureEnd : " << endLecture << " startLecture : " << startLecture << "\n";
}
return 0;
}
이제 회의가 끝나는 시간을 기준으로 가장 낮은 회의를 선택하고 선택한 회의의 끝나는 시간보다 일찍 시작하는 회의를 리스트에서 제외하면 될 것 같다.
#include <iostream>
#include <queue>
using namespace std;
priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> myQueue, myQueue2;
int result = 0;
int startLecture = 0;
int endLecture = 0;
int N = 0;
void Initializtion()
{
cin >> N;
while (N > 0)
{
cin >> startLecture >> endLecture;
// 강의가 끝나는 시간을 낮은 값으로 정렬
myQueue.push(make_pair(endLecture, startLecture));
N--;
}
}
int main()
{
Initializtion();
pair<int, int> temp;
while (!myQueue.empty())
{
// 강의가 끝나는 시간
endLecture = myQueue.top().first;
//cout << " 등록된 강의 : " << "myQueue.top().first : " << myQueue.top().first << " myQueue.top().second : " << myQueue.top().second << "\n";
myQueue.pop();
result++;
// pair 끝나는 시간 / 시작 시간
while (!myQueue.empty())
{
temp = make_pair(myQueue.top().first, myQueue.top().second);
myQueue.pop();
//cout << " 시작시간 : " << temp.second << " 끝나는 시간 : " << temp.first << "\n";
if (temp.second < endLecture)
{
}
else
{
myQueue2.push(temp);
}
}
myQueue = myQueue2;
myQueue2 = priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>();
}
cout << result;
return 0;
}틀린 코드
#include <iostream>
#include <queue>
using namespace std;
priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> myQueue, myQueue2;
int result = 0;
int startLecture = 0;
int endLecture = 0;
int N = 0;
void Initializtion()
{
cin >> N;
while (N > 0)
{
cin >> startLecture >> endLecture;
myQueue.push(make_pair(endLecture, startLecture));
N--;
}
}
int main()
{
Initializtion();
while (!myQueue.empty())
{
endLecture = myQueue.top().first;
myQueue.pop();
result++;
myQueue2 = myQueue;
myQueue = priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>();
while (!myQueue2.empty())
{
// 다음 강의는 지금 강의가 끝나는 시간보다 같거나 커야함
if (myQueue2.top().second >= endLecture)
{
myQueue.push(myQueue2.top());
}
myQueue2.pop();
}
}
cout << result;
return 0;
}시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과 시간 초과
더 유연한 생각이 필요하다
아마 큐에 다시 넣는 부분이 문제인 것 같다. 테스트 케이스는 맞으나 시간 초과로 고통 받는다. 이 방법은 버리기로 함 멀티 맵으로 바꾸는 것이 좋은 방법인 것 같다. => (무슨 정신 머리로 이런 생각을 했는지 의문)
계속되는 실패에 처음으로 돌아감
고민하다 계속 큐에 넣어야 하는가????? 너무 비효율적이다 생각 int로 현재 강의가 끝나는 지점만 알면 되는 것 아닌가????
통과된 코드
#include <iostream>
#include <queue>
using namespace std;
// 우선 큐로 정렬 강의가 끝나느 시간을 오름차순으로 정렬
priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> myQueue;
int result = 0;
int startLecture = 0;
int endLecture = 0;
int N = 0;
// 조건 초기화
void Initializtion()
{
cin >> N;
while (N > 0)
{
cin >> startLecture >> endLecture;
myQueue.push(make_pair(endLecture, startLecture));
N--;
}
}
int main()
{
Initializtion();
// 현재 진행 중인 강의가 끝나는 시간으로 생각
int curEndLecture = 0;
// 끝나는 시간이 가장 빠른 강의를 가져옴
curEndLecture = myQueue.top().first;
myQueue.pop();
result++;
// 주어진 강의를 모두 확인할 때까지 반복
while (!myQueue.empty())
{
endLecture = myQueue.top().first;
startLecture = myQueue.top().second;
myQueue.pop();
// 끝나는 시간이 빠른 강의 들의 시작 시간을 확인
// 강의의 시작 시간이 끝나는 시간과 같거나 늦으면
// 현재 진행 중인 강의의 인덱스를 바꾸어줌
// (강의를 진행한다는 의미)
if (startLecture >= curEndLecture)
{
curEndLecture = endLecture;
result++;
}
}
cout << result;
return 0;
}