강의실 배정 #11000

 

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

11000번: 강의실 배정

 

 

제약을 살펴보면,

256 MB로는 10^8 바이트 => 100MB  10^9 Si Ti 를 인덱스로 담기 불가능하다.

그럼 DP는 아니고, Greedy이다.

 

수업 시작시간, 끝시간을 기준으로 sorting하는 것은 O(logN=200000) 이므로 연산시간이 적으니, 부담없이 사용할 수 있다.

 

 

조건 1. Ti <= Sj 일때는 한 강의실을 사용할 수 있다.

고민을 거듭해보니, 끝 시간을 유지할 다른 자료구조가 필요함을 느꼈다.

중간과정 시간초과나는 풀이.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

bool comp(int a, int b) {
	return a > b;
}

//long long arr[1000000000];
int main() {


	int  n;
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n; //1 ≤ N ≤ 200,000
	vector<pair<int, int>> v;
	//priority_queue<int, vector<int>, greater<<int>>
	int cnt = 0;

	for (int i = 0; i < n; i++) {
		int s, t;
		cin >> s >> t;
		v.push_back(make_pair(s, t));
	}
	sort(v.begin(), v.end());
	
	vector<int> v2;
	v2.push_back(v[0].second);

	for (int i = 1; i < v.size(); i++) {//20만

		if (v2[0] <= v[i].first) {
			//sort(v2.begin(), v2.end(), comp);
			v2.erase(v2.end()-1);
			v2.push_back(v[i].second);
			
			//cnt++;
			//cout << v2[0] << endl;
			
		}
		else {
			v2.push_back(v[i].second);
			
			//cout << v2[0] << endl;

		}
		sort(v2.begin(), v2.end(), comp);
		 
	}
	//for (int i = 0; i < v.size()-1; i++)
	//	cout << v2[i] << endl;
	cout << v2.size();
	return 0;
	}

 

 

sorting을 계속 돌리다보니, 시간초과가 난 것 같다. 다른 방법이 필요함을 느꼈다.

 

 

나의 좁은 식견으로는 태그를 보지 않고 우선순위 큐를 떠올리는 것이 불가능했다. 인터넷을 찾아보니 자료구조를 활용하시는 실력이 다들 대단하신 것 같고 부족함을 느꼈다. 모든 분이 같은 생각을 하신 것 같다.

 

그래서 나도 우선순위 큐를 이용해 보기로 했다. 음. Algorithm 의 sort 함수의 시간복잡도와 우선순위 큐의 삽입 시간복잡도가 같아서 의아했다.

 

알아본 결과 C++에서 sort 의 시간복잡도는 N logN 이며, priority_queue의 경우 push,pop의 시간 복잡도는 log N이라고 한다. 따라서 우선순위 큐를 쓸수밖에 없는 문제라고 결론을 내렸다.

이제 이해의 영역을 넘어선 암기로..

 

따라서 코드는 vector v2 부분을 우선순위 큐의 push pop 으로 대체해주면 된다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
int N;
int answer;
vector<pair<int, int>> v;
priority_queue<int, vector<int>, greater<int>> pq;
 
int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        int start, end;
        cin >> start >> end;
        v.push_back({ start,end });
    }
  
    sort(v.begin(), v.end()); 
 
    pq.push(v[0].second);
    for (int i = 1; i < v.size(); i++) {
        if (v[i].first >= pq.top()) {
            pq.pop();
            pq.push(v[i].second);
        }
        else {
            pq.push(v[i].second);
        }
    }
    cout << pq.size();
}