ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 11000
    알고리즘/acmicpc 2015. 10. 11. 15:00
    최소 강의실의 개수를 구하는 문제.

    먼저 수업들을 시작 시간을 기준으로 다시 정렬을 해두자. class[]

    그리고 현재 강의실중 가장 수업이 빨리 끝나는 강의실을 관리하는 자료구조를 가지고 있다고 하자. (우선순위 큐를 이용해서 관리하는게 좋다)


    정렬된 배열 class[] 에 있는 i번째 수업을 내가 추가하고자 한다면

    현재 강의실 중에서 가장 수업이 빨리 끝나는 강의실에 추가하는 것이 최적의 경우일 것이다.


    만약 i번째 수업의 시작시간이 가장 수업이 빨리 끝나는 강의실의 끝나는 시간보다 더 일찍 시작한다면, i번째 수업은 반드시 강의실을 추가해서 들을 수밖에 없다. 다른 강의실들은 가장 수업이 빨리 끝나는 강의실보다 더 늦게 끝날 것이 분명하기 때문이다.


    우선순위큐와 정렬을 적당히 활용해서 풀면 쉽게 풀수 있다.




     
    #include<cstdio>
    #include<algorithm>
    #include<vector>
    #include<queue>
    
    using namespace std;
    
    vector<int> rooms;
    vector<pair<int, int> > c;
    
    int main(){
    	
    	int n, from, to;
    	scanf("%d", &n);
    
    	for(int i=0; i<n; i++){
    		scanf("%d %d", &from, &to);
    		c.push_back(make_pair(from, to));
    	}
    	sort(c.begin(), c.end());
    
    	priority_queue<int > pq;
    	pq.push(0);
    	for(int piv=0; piv < c.size(); piv++){
    		int cur_finish = -pq.top();
    		if(c[piv].first < cur_finish){
    			pq.push(-c[piv].second);
    		}
    		else{
    			cur_finish = -c[piv].second;
    			pq.pop();
    			pq.push(cur_finish);
    		}
    	}
    
    	printf("%d\n", pq.size());
    	return 0;
    }
    

    '알고리즘 > acmicpc' 카테고리의 다른 글

    2590  (0) 2015.10.15
    1931  (0) 2015.10.14
    11000  (0) 2015.10.11
    2405  (0) 2015.10.09
    2437  (0) 2015.10.09
    2616  (0) 2015.10.03

    댓글 0

Designed by Tistory.