강의실 배정

https://www.acmicpc.net/problem/11000

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	25367	7462	5481	28.998%

문제

수강 신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 
김종혜 선생님한테는 S_i에 시작해서 T_i에 끝나는 N개의 수업이 주어지는데,
최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 
참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다.
(즉, T_i ≤ S_j 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)
수강 신청 대충 한 게 찔리면, 선생님을 도와드리자!

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)
이후 N개의 줄에 S_i, T_i가 주어진다. (0 ≤ S_i < T_i ≤ 10⁹)

출력

강의실의 개수를 출력하라.

예제 입력 1

3
1 3
2 4
3 5

예제 출력 1

2

출처

• 문제를 만든 사람: koosaga
• 데이터를 추가한 사람: zlzmsrhak

알고리즘 분류

• 자료 구조
• 그리디 알고리즘
• 정렬
• 우선순위 큐

---

추가 반례

예제 입력 A

5
1 7
2 3
3 4
4 8
7 10

예제 출력 A

2

예제 입력 B

3
999999999 1000000000
999999998 999999999 
1 999999998

예제 출력 B

1

예제 입력 C

3
999999999 1000000000
999999998 999999999 
1 999999998

예제 출력 C

1

예제 입력 D

4
1 2
1 4
2 6
4 5

예제 출력 D

2

예제 입력 E

6
4 12
7 11
9 10
7 8
2 5
1 3

예제 출력 E

3

Si ~ Ti에 끝나는 N개의 수업

최소의 강의실을 사용하여 모든 수업을 한다

수업이 끝난 직후에 다음 수업을 시작할 수 있다.

즉 Ti <= Sj 일 경우 i 수업과 j수업을 같이 들을 수 있다.

1 ≤ N ≤ 200,000

0 ≤ Si < Ti ≤ 109

무슨 소리야?

항상 문제를 이해하는 것이 가장 어렵다

멀티맵의
key 값을 시작 값
value값을 끝나는 값으로 설정하면서
해당 value 값과 다른 key 값이 같으면 해당 맵을 지우고 value를 바꾸어주면 어떨까?

#include <iostream>
#include <map>

using namespace std;

multimap<int, int> curriculum;

void Initialization()
{
	int N = 0;
	int S = 0;
	int T = 0;
	cin >> N;

	while (N > 0)
	{
		cin >> S >> T;
		curriculum.insert({ S,T });
		N--;
	}
}

int main()
{
    // 초기화
	Initialization();
    
    // 멀티맵 출력 
	for (auto& elem : curriculum)
	{
		cout << " S : " << elem.first << " T : " << elem.second << "\n";
	}

	return 0;
}

틀린 코드 1

#include <iostream>
#include <map>

using namespace std;

multimap<int, int> curriculumMultiMap;
multimap<int, int>::iterator it;

int result = 0;

void Initialization()
{
	int N = 0;
	int S = 0;
	int T = 0;
	cin >> N;
	result = N;
	while (N > 0)
	{
		cin >> S >> T;
		curriculumMultiMap.insert({ S,T });
		N--;
	}
}

int main()
{
	Initialization();
	
	// key 값이 낮은 값부터 시작
	for (auto& elem : curriculumMultiMap)
	{
		//cout << " S : " << elem.first << " T : " << elem.second << "\n";
		for (it = curriculumMultiMap.lower_bound(elem.second);it != curriculumMultiMap.end(); it++)
		{
			elem.second = it->second;
			cout << elem.second;
			result--;
			curriculumMultiMap.erase(it->first);
		}
	}
	cout << result;
	return 0;
}

wordbe.tistory.com/entry/STL-erase <- 참고글

연관 컨테이너의 경우(Associate container)
: set, map, multiset, multimap의 경우.
컨테이너의 어떤 요소가 erase 될 때, 이 요소를 가리키고 있는 모든 반복자들이 무효화됩니다.
c.erase(i)가 복귀하자마자 i는 바로 무효화됩니다.
따라서 루프에 있는 ++i는 무효화되어 에러가 납니다.
이를 해결하기 위해서는,
erase를 호출하기 전에 반복자 i가 c의 다음 요소를 가리키도록 세팅하면 됩니다.

틀린 코드 2

#include <iostream>
#include <map>

using namespace std;

multimap<int, int> curriculumMultiMap;
int result = 0;

void Initialization()
{
	int N = 0;
	int S = 0;
	int T = 0;
	cin >> N;
	while (N > 0)
	{
		cin >> S >> T;
		curriculumMultiMap.insert({ S,T });
		N--;
	}
}

int main()
{
	Initialization();

	for (auto& elem : curriculumMultiMap)
	{
		cout << "elem.first" << elem.first << "\n";
		for (auto it = curriculumMultiMap.lower_bound(elem.second);it != curriculumMultiMap.end();)
		{
			if (elem.second <= it->first)
			{
				cout << "elem.first : " << elem.first << " elem.second : " << elem.second << " it->first : " << it->first << " it->second : " << it->second << "\n";
				elem.second = it->second;
				curriculumMultiMap.erase(it++);
			}
			else
			{
				it++;
			}
		}
		result++;
	}



	cout << result;
	return 0;
}

multimap으로 풀었지만 시간 초과 벗어날 수 없어서 포기….
insert
erase
의 속도가 느리다…

시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간

틀린 코드 3

#include <iostream>
#include <set>
#include <queue>

using namespace std;

priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> myQueue;

int result = 1;
pair<int, int> mypair;
multiset<int> mymultiset;

void Initialization()
{
	int N = 0;
	int S = 0;
	int T = 0;
	
	cin >> N;
	while (N > 0)
	{
		cin >> S >> T;
		myQueue.push(make_pair(S, T));
		N--;
	}
}

int main()
{
	Initialization();
	mypair = myQueue.top();
	myQueue.pop();
	mymultiset.insert(mypair.second);

	while (!myQueue.empty())
	{
		mypair = myQueue.top();
		myQueue.pop();
		for (auto iter = mymultiset.begin();iter != mymultiset.end();iter++)
		{
			if (mypair.first < *iter)
			{
				mymultiset.insert(mypair.second);
				result++;
				break;
			}
			
			if (mypair.first >= *iter)
			{
				mymultiset.erase(*iter);
				mymultiset.insert(mypair.second);
				break;
			}
		}
	}
	
	cout << result;
	return 0;
}

우선 수업들을 Priority_Queue에 넣고 강의의 시작 시간을 기준으로 오름차순 정렬해준다. 
(내 풀이에서는 7 8 / 7 11의 순서는 의미가 없다.)

처음에는 무조건 Priority_Queue에서 하나의 pair 값을 꺼내고 Multiset에 강의가 끝나는 시간을 넣어준다.

그 다음 Priority_Queue에서 하나의 pair 값을 꺼내고
강의 시작 시간(first)과 Multiset에서 가장 작은 수와 비교한다.
만약 강의의 시작 시간이 Multiset의 가장 낮은 수와 비교하여 작을 경우 강의실에 끝나는 시간을 추가해준다.

그 다음 Priority_Queue 에서 하나의 pair 값을 꺼내고
강의 시작 시간(first)과 Multiset에서 가장 작은 수와 비교한다.
만약 강의의 시작 시간이 Multiset의 가장 낮은 수와 비교하여 크다면
Multiset에서 강의 시작 시간(first) 보다 작거나 같은 수 중에서 제일 높은 숫자를 Multiset에서 지우고
-> 강의가 끝나고 같은 강의실에서 다음 수업을 진행한다는 의미
강의가 끝나는 시간을 Multiset에 추가한다.

해당 과정을  Queue가 비어있을 때까지 진행한다.

알고리즘을 생각하는 시간보다 iterator 사용법을 익히는 시간이 더 들었다.

통과된 코드

#include <iostream>
#include <set>
#include <queue>

using namespace std;

//우선 순위 Q를 사용하여 입력값을 정렬해준다.
priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> myQueue;

int result = 1;

// 강의들을 저장해 놓음
pair<int, int> mypair;

// 멀티맵을 사용하기 위한 준비
multiset<int> mymultiset;
multiset<int>::iterator iter;

// 입력값 초기화 함수
void Initialization()
{
	int N = 0;
	int S = 0;
	int T = 0;
	cin >> N;
	while (N > 0)
	{
		cin >> S >> T;
		myQueue.push(make_pair(S, T));
		N--;
	}
}

int main()
{
	// 입력값을 받아줍니다.
	Initialization();
	mypair = myQueue.top();
	myQueue.pop();
	mymultiset.insert(mypair.second);

	while (!myQueue.empty())
	{
		mypair = myQueue.top();
		myQueue.pop();
	 
		if (mypair.first < *mymultiset.begin())
		{
			mymultiset.insert(mypair.second);
			result++;
			continue;
		}

		iter = mymultiset.lower_bound(mypair.first);

		// 값이 같을 때도 같이 set에서 제거하고 페어를 추가해준다.
		if (*iter == mypair.first)
		{
			mymultiset.erase(iter);
		}
		else
		{
			mymultiset.erase(--iter);
		}
		
		mymultiset.insert(mypair.second);
	}
    
	cout << result;
    
	return 0;
}