회의실 배정
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 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;
}
![백준 1967번 (트리의 지름, C++) [BAEKJOON]](https://lycos7560.com/wp-content/uploads/boj-og.png)