[C++][BOJ] 1931 회의실 배정 :: 라인 스위핑

구간이 나오면 정렬!을 떠올리자. 어느정도의 복잡도를 감소시킬 수 있다.

 

[문제]

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

 

각 회의에 대해 시작시간과 끝나는 시간이 주어져 있을 때,

각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾자.

 

회의의 수 N(1 ≤ N ≤ 100,000)

시작 시간과 끝나는 시간은 2^31-1보다 작거나 같은 자연수 또는 0

 

[해결방법]

회의의 수가 최대 100,000 개 이므로 완전탐색으로는 풀 수 없다. Greedy 로 풀어야 한다.

특히, 구간이 주어지면 정렬을 생각하자. 라인스위핑 문제라 부른다.

 

1) 시작 시간을 기준으로 정렬

2) 끝나는 시간을 기준으로 정렬

3) 회의 시간을 기준으로 정렬

 

위 3가지 처럼 모든 풀이방법을 생각하며 어떻게 풀어야 할지를 고민해보자.

 

그림에 2가지 경우가 그려져 있는데, 윗 부분은 start, end 시간을 기준으로 선택한 경우다.

start 시간을 기준으로 하면 2개밖에 선택이 안되는데, end 시간을 기준으로 하면 3개 선택 가능하다. size를 기준으로 해도 3개 선택이 가능하다.

 

아래 부분은 size를 기준으로 했을 때의 반례이다. size 를 기준으로 하면 1개 밖에 선택이 안된다. end 시간을 기준으로 해야 2개가 선택 가능하다.

 

즉, 회의실 배정문제는 end 시간을 기준으로 정렬하여 선택해야 정확한 풀이가 가능하다. 정렬은 custome sort 함수를 만들거나 start 시간과 end 시간 위치를 바꿔서 vector pair 에 저장하여 sort 할 수 있다.

 

* 최종결론: end 시간을 기준으로 정렬하고 이전 회의가 끝나는 시간 이후에 시작하는 회의만 선택하여 최대 개수를 구하자. 

 

 

[반례]

3
0 0
0 0
0 0
---
3

3
4 4
3 4
2 4
---
2

 

 

[코드]

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

// Custom Sort 함수
bool SortPairSecond(const pair<int, int>& left, const pair<int, int>& right) {
	if (left.second == right.second) {
		return left.first < right.first;
	}
	return left.second < right.second;
}

int main() {
	int meetingNum, startNum, endNum, count = 0;
	vector<pair<int, int>> meetings; // startTime, endTime

	cin >> meetingNum;
	for (int i = 0; i < meetingNum; i++) {
		cin >> startNum >> endNum;
		meetings.push_back({ startNum, endNum });
	}
	sort(meetings.begin(), meetings.end(), SortPairSecond);

	// 시작값 일단 넣고 비교 시작
	int meetingEndTime = meetings[0].second;
	count++;

	for (int i = 1; i < meetings.size(); i++) { 
		if (meetings[i].first >= meetingEndTime) { // 이전 회의가 끝나는 시간 이후에 시작하는 회의만 가능함
			meetingEndTime = meetings[i].second;
			count++;
		}
	}
	cout << count << "\n";

	return 0;
}