[ 백준 ] 1931번 그리디 - 회의실 배정

 

 

문제

 

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

입력

 

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

 

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

using namespace std;

int main()
{
	int num = 0;
	cin >> num;

	int a, b = 0;
	int count = 1;
	int time = 0;

	vector<pair<int, int>> arr;

	for (int i = 0; i < num; i++)
	{
		cin >> a >> b;
		arr.push_back(pair<int, int>(b, a));
	}

	sort(arr.begin(), arr.end());

	time = arr[0].first;

	for (int j = 1; j < num; j++)
	{
		if (time <= arr[j].second)
		{
			count++;

			time = arr[j].first;
		}
	}

	cout << count << endl;

	return 0;
}

 

문제 풀이

 

1. 회의가 끝나는것과 동시에 다음 회의가 시작 될 수 있음

2. 회의의 시간과 끝나는 시간이 같을 수 있음

3. 최대로 회의를 많이 하는 방법을 구하기

 

⭐ 회의시간이 빠른 순으로 하더라도 회의가 늦게 끝나는 경우엔 최대의 회의 수가 나올 수 없다.

      => 회의시간의 종료시점이 매우 중요

 

2차원 백터를 선언하여 넣으려고 했으나 정렬에서 문제가 생겼었다. 

알아보는 중 백터의 pair을 사용하여 쌍으로 값을 저장할 수 있다는 것을 알게 되었고 이를 사용하였다.

 

pair<[Type],[Type]>

- 2개의 지정한 타입을 저장

- 2개의 연관된 값을 같이 저장하여 관리 가능

- .first와 .second로 각각 접근 가능

 

여기서 백터에 저장된 값을 빠르게 끝나는 종료 시점으로 정렬을 하였다.

 

- time 변수 : 종료시간이 빠른 순으로 초기화

- time 변수와 다음 스케줄의 시작 시점과 크거나 같은지 비교