C++ / 1931 / 회의실 배정 ( 그리디 알고리즘 )

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

 

 

 

문제 요약

총 회의의 수 n과 시작시간과 끝나는 시간을 입력받아 최대 사용할 수 있는 회의의 개수를 출력 해야합니다.

 

문제 풀이

1. 2차원 백터로 회의의 끝나는 시간과 시작 시간을 입력받습니다.

2. 재각각인 회의 시간을 끝나는 시간별로 정렬 합니다.

3. 비교할 시간을 담을 변수에 초기에 비교할 시간을 저장합니다.

4. 반복문안에서 조건문으로 시간을 담은 변수와 그 다음 강의의 시작 시간을 비교합니다.

5. 시작시간이 기존에 저장한 시간보다 클 경우 변수에 새로 저장합니다.

 

주의할 점

정렬을 할 때 처음엔 선택정렬로 정렬 하였으나 자꾸 시간 초과가 발생하였습니다.

algorithm 헤더 파일에 있는 sort() 함수를 사용해 해결하였습니다.

코드

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

int n;
int a, b;
int ptr;
int tmp[1][1];
int sum = 0;

int main()
{
	cin >> n;
    // 2차원 백터
	vector<pair<int,int>> p;
	for (int i = 0; i < n; i++)
	{

		
		cin >> a;
		cin >> b;
		// 끝나는 시간을 첫번째 인자로 입력
        p.push_back(make_pair(b, a));
	}
	// 끝나는 시간 순으로 정렬
	sort(p.begin(), p.end());
	
    // 비교할 시간 저장
	ptr = p[0].second;
    
	for (int i = 0; i < n; i++)
	{
    	// 끝나는 시간과 다음 강의 시작시간을 비교
        // 다음 강의의 시작시간이 크거나 같은경우 실행
		if (ptr <= p[i].second)
		{
         	// 강의의 끝나는 시간을 저장
			ptr = p[i].first;
			sum++;
		}
	}
	// 출력
	cout << sum;
	return 0;
}

 

 

반응형

예제 입력

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

결과