[C/C++] 백준 1931번 - 회의실 배정 (그리디 알고리즘)

 

예제에서 주어진 입력을 시각화 하면 위와 같은 스케줄 표가 나온다. 

문제에서 조건은

1. 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수 찾기
2. 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.
3. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

2번, 3번 항목을 살펴보면 만약 2 2 와 1 2가 입력으로 주어진다면 1~2에서 회의를 진행하고 회의가 끝나는 즉시 2 2회의를 진행해서 바로 끝내는 경우가 발생할 수도 있다는 얘기이다. 

문제풀이의 핵심은 시작하는 시간이 빨라도 늦게 끝나면 최대 회의의 수를 맞출 수 없다는 점이므로 각각의 스케줄에서 회의의 종료시간이 중요하게 작용한다.

따라서 vector 컨테이너에 회의 스케줄을 저장하고 각각의 스케줄의 종료시점에 대해 정렬을 한 뒤 

1. 첫번째 time 변수는 종료시간이 가장 빠른 스케줄의 종료시점으로 초기화한다.

2. 두번째 스케줄의 시작 시점이 첫번쨰 스케줄의 종료시점보다 크거나 같은지 확인한다. 

if (두번째 스케줄의 시작 시점 >= 첫번째 스케줄 종료 시점)

    => time 변수를 두번째 스케줄의 종료 시점으로 저장

    => count 수를 +1만큼 올림

else

    다음 스케줄로 넘어간다.

3. 모든 스케줄을 확인할 때 까지 2번을 반복한다.

 

<코드>

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

int value[10];

int main()
{
	int N, end, begin;

	vector<pair<int, int>> schedule;

	cin >> N ;

	for (int i = 0; i < N; i++)
	{
		cin >> begin >> end;
		schedule.push_back(make_pair(end, begin));
	}
	
	sort(schedule.begin(), schedule.end());
	
	int time = schedule[0].first;
	int count = 1;
	for (int i = 1 ;i < N; i++) 
	{
		if (time <= schedule[i].second )
		{
			count++;
			time = schedule[i].first;
		}
	}

	cout << count;
}

 

 

 

 

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

1931번: 회의실배정