03.06. 강의실 배정[Greedy Algorithm][백준 11000]

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

11000번: 강의실 배정

 

Algorithm classification : Greedy Algorithm, Sorting, Data Struture, Priority Queue

 

03.06.1. Problem

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.

김종혜 선생님한테는 S_i에 시작해서 T_i에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, T_i ≤ S_j 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

 

03.06.2. Input limit

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 S_i, T_i가 주어진다. (0 ≤ S_i < T_i ≤ 10^9)

 

03.06.3. Output

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

 

03.06.4. Solution

조금 어려운 난이도일 수 있습니다. 앞서 소개해드렸던 문제보다 더 많은 지식 베이스를 요구합니다. 앞선 포스트에서 소개해드렸던 문제와 유사합니다. 시작하는 시간이 가장 빠른 강의부터 진행하면 됩니다. 만약 비어있는 강의실이 있다면 진행하고 없다면 새로운 강의실을 추가하는 방식으로 풀면 될 것입니다. 만약 시작하는 시간이 가장 빠른 강의부터 비어있는 강의실에 넣지 않는다면 선택을 받지 못한 그 강의는 다른 강의실에 추가되어야만 하고 그렇다면 필요한 강의실의 갯수가 늘어나겠죠. 

	for(i = 0; i < n; i++){
		scanf("%d %d", &s, &e);
		v.push_back(pair<int,int>(e,s));
	} 
	sort(v.begin(), v.end());
	int temp;
	while(v.size()){
		//printf("%d",v.size());
		temp = v[0].first;
		v.erase(v.begin());
		for(i = 0; i < v.size(); i++){
			if(temp <= v[i].second){
				temp = v[i].first;
				v.erase(v.begin() + i);
			}
		}
		c++;
	}