[백준알고리즘] 1931번: 회의실 배정 -C++

[백준알고리즘] 1931번: 회의실 배정 -C++

1931번: 회의실 배정 (acmicpc.net)

1931번: 회의실 배정

주어진 회의 시간들이 주어진 가운데, 가장 많은 회의를 처리할 수 있도록 사용 시간을 배정하면 된다.

 

예전에 파이썬으로 푼 적이 있으며, 풀이는 아래의 링크에 포스팅했다.

[백준알고리즘] 1931번: 회의실배정 -Python (tistory.com)

[백준알고리즘] 1931번: 회의실배정 -Python

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

---

 

이 문제는 대표적인 그리디 문제 중에 하나이다.

 

문제에서 주어진 조건을 살펴보면 아래와 같이 정리가 가능하다.

• 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.
• 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

위의 조건을 만족하면서 가장 많이 회의가 가능한 스케줄을 만들면 된다.

 

이 문제를 풀 때는 생각보다 쉽게 풀린다. 일상 생활에서도 쉽게 생각할 수 있는 방법이다.

보통 학생의 경우 숙제를 하거나 회사에서 여러 업무를 맡은 경우에 일을 처리할 때 어떻게 처리하나 생각해보자. 보통은 숙제를 하는 경우에 제출일이 빠른 것부터 할 것이다. 마찬가지로 업무를 여러 개 맡는다고 생각해보면 기간이 빠른 것부터 처리할 것이다. 물론 무조건은 아니지만.

 

하지만, 여기서 문제의 조건 중에 한 번 시작하면 중간에 중단될 수 없다는 조건이 있기 때문에 이것도 고려해서 다시 생각해보자.

 

한 번 숙제를 시작하면, 그 숙제를 다 끝낸 뒤에 다른 숙제를 할 수 있다고 생각해보자. 3월 2일에서 7일까지 해야하는 숙제 하나 하려고 3월 3일에서 5일까지, 그리고 5일에서 6일까지 해야 하는 숙제 두 개를 포기하는 것을 고려해봐야 한다는 것이다. 숙제의 가치가 동일할 때 빨리 시작한다고 중요한 것이 아니라 빨리 끝내서 다른 것도 더 할 수 있도록 해야 하는 것이다.

 

어차피 3월 2일에서 7일까지 하는 숙제를 한다면, 7일까지는 아무 일도 못한다. 동일하게 3월 3일에서 5일까지 하는 숙제를 한다면 5일까지는 아무 일도 못한다. 하지만, 무엇이든 할 수 있는 시간이 후자의 경우가 더 많은 것이다.

 

이러한 개념을 이용해 그리디하게 문제를 풀면 된다.

 

즉, 가장 빨리 끝나는 회의들을 이전 회의와 겹치지 않는 선에서 순차적으로 선택하면 된다.

 

아래는 해당 방법으로 푼 C++ 코드다. compare함수를 직접 정의해서 sort의 인자로 넣어주었다. 그렇게 끝나는 시간을 기준으로 오름차순 정렬을 한 뒤, 마지막 회의 끝나는 시간 이후에 시작하는 회의를 찾는 과정을 반복해주었다.

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

void solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false); 
	std::cin.tie(NULL); 
	std::cout.tie(NULL); 
	
	solve();
}

bool compare(std::pair<int, int> p1, std::pair<int, int> p2) // true면 안 바꿈
{
	if (p1.second == p2.second)
		return p1.first < p2.first;

	return p1.second < p2.second;
}

void solve(void)
{
	int n;
	std::cin >> n;

	std::vector<std::pair<int, int>> vecUsedTime(n);
	for (auto& pair : vecUsedTime)
		std::cin >> pair.first >> pair.second;

	std::sort(vecUsedTime.begin(), vecUsedTime.end(), compare);
	
	int lastTime = 0;
	int count = 0;
	for (auto& pair : vecUsedTime)
	{
		if (pair.first < lastTime)
			continue;

		lastTime = pair.second;
		count++;
	}

	std::cout << count;
}