회의실 배정

www.acmicpc.net/problem/1931

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	144010	45043	31834	29.573%

문제

한 개의 회의 실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여
회의실 사용 표를 만들려고 한다.
각 회의 I에 대해 시작 시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서
회의 실을 사용할 수 있는 회의의 최대 개수를 찾아보자.
단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에
다음 회의가 시작될 수 있다.
회의의 시작 시간과 끝나는 시간이 같을 수도 있다.
이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다.
둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고
회의의 시작시간과 끝나는 시간이 주어진다.
시작 시간과 끝나는 시간은 2³¹-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) 를 이용할 수 있다.

출처

• 빠진 조건을 찾은 사람: andy627
• 데이터를 추가한 사람: jws0324, kimchangyoung, rosedskim

알고리즘 분류

• 그리디 알고리즘
• 정렬

---

추가 예제

예제 입력 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;
}