백준 1931 회의실 배정 c++

그리디 알고리즘이고

사용할 수 있는 회의실의 최대 개수를 출력하면 된다

 

 

알고리즘 시간에 본 적 있는 유형인데

Interval Scheduling Problem이다

 

 

자료에서 힌트를 얻어

끝나는 시간이 제일 빠른 거 부터 고르는 알고리즘을 선택했다

 

 

 

 

 

시간 초과난 코드

#include <iostream>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	int n,count=0;
	cin >> n;
	int endindex=0,startindex=0;
	

	int** schedule = new int* [n];
	for (int i = 0; i < n; i++) {
		schedule[i] = new int[2];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 2; j++) {
			cin >> schedule[i][j];
		}
	}

	
	while (true) {

		bool fullcheck = false;	//한번이라도 조건을 만족하는지 체크(방을 쓸수있는지)

		if (count == 0)
			fullcheck = true;

		for (int i = 1; i < n; i++) {
			if (count == 0 && schedule[endindex][1] > schedule[i][1] ) {	//가장빨리끝나는 시간찾음
				endindex = i;
				fullcheck = true;
			}
			
			else if(count>=1 && schedule[endindex][1]<=schedule[i][0] && fullcheck==false){	//시작시간이 그 전 회의시간보다 뒤여야함
				endindex = i;
				fullcheck = true;
			}
			else if (fullcheck == true) {		//한번 왔을때 끝나는시간이 최소인걸 찾는다
				if (schedule[endindex][1] > schedule[i][1]) {
					endindex = i;
				}

			}
		}
		if (fullcheck)
			count++;
		else
			break;
	}

	cout << count;

	return 0;
}

n을 입력받으면

arr[n][2]를 동적할당해

입력받아 주고

반복문을 돌며

가장 끝나는 시간이 빠른거 고르고, 다시 고르고 

이렇게했더니 시간 초과가났다

 

 

 

 

곰곰히 고민하다

모르겠어서

자료를 다시 봤다

 

 

나는

정렬을 하지 않고

일일히 찾아서 오래 걸렸던 것 같다

먼저 완료 시간 순서대로 정렬 하고,

가장 빠른 것을 고르고 그 다음 겹치지않는 가장 빠른 것을 고르면

O(n)만 소요된다

 

기존에 내가 짰던 코드는 O(N^2)이였나 보다 

 

 

그래서 정렬을 쓰려면

vector를 써야겠다하고 짜봤는데

sort()의 cmp부분을 혼자 못짜겠어서

구글링을 했다

 

 

그래서 이걸 내가 짰다고 말하기도 참 부끄럽긴하다

알고리즘이랑 벡터사용도 다 찾아봤으니..

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


bool cmp(pair<int, int> start ,pair<int,int> end);

int main() {
	vector<pair<int, int>> time;
	int n,start,end,count=0,room;
	cin>>n;

	for (int i = 0; i < n; i++) {
		cin >> start>>end;
		time.push_back(make_pair(start, end));
	}
	sort(time.begin(),time.end(),cmp);

	
	room = 0;
	count++;

	for (int i = 1; i < n; i++) {
		if (time[room].second <= time[i].first) {
			room = i;
			count++;
		}
	}
	
	cout << count;
	
}

bool cmp(pair<int, int> start, pair<int, int> end) {


	if (start.second == end.second) {
		return start.first < end.first;
	}
	else {
	return start.second < end.second;
	}
}

 

 

2차원 벡터일때 cmp 쓰는법

bool cmp(pair<int,int> start, pair<int,int> end){

 

if(start.second==end.second){

     return start.first<end.first;

}

 

return start.second<end.second;

 

}

 

 

다음엔 잊어먹지말자