[BOJ] 1931 - 회의실 배정

Sierra·2022년 1월 16일
0

[BOJ] Greedy

목록 보기
2/33
post-thumbnail

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

문제

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

입력

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

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

예제 입출력

  • 예제 입력 1
11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14
  • 예제 출력 1
4

Solution

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

void init() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
}

int main() {
	init();
	int N;
	cin >> N;
	vector<pair<int, int>> data(N);
	for (int i = 0; i < N; i++) {
		cin >> data[i].second >> data[i].first;
	}
	sort(data.begin(), data.end());
	int time = 0;
	int answer = 0;
	for (int i = 0; i < N; i++) {
		if (time <= data[i].second) {
			time = data[i].first;
			answer += 1;
		}
	}
	cout << answer << '\n';
}

시작 시간과 끝 시간이 입력으로 주어진다. 가장 많은 회의가 회의실에서 진행이 되어야 회사 입장에서는(?) 이득일테니 그걸 구해보라는 문제다.

C++ 에서 pair 구조의 정렬을 진행할 때 일단 기본값으로는 first 를 기준으로 정렬이 되기는 한다.
우선 언제 회의가 시작하는 지 기준으로 정렬을 해본다. 가장 빨리 끝나는 사람들을 기준으로 판단하는 게 훨씬 좋기 때문이다.

언제 회의가 시작되는 지를 기준으로 판단하게 된다면 문제점이 몇 개 생긴다. 언제 끝나는 지가 다 다르다보니 예를 들어 최대한 빠르게 끝난 사람을 먼저 빼고 그 다음으로 최대한 빨리 다음에 진행하는 회의를 하려고 한다 치자. 만약 회의가 빨리 시작했지만 늦게 끝날 수도 있는 것 아닌가. 시작하는 시간이 아무리 빨라도 늦게 끝나면 의미가 없다.

그래서 시작하는 시간 기준으로 데이터를 정렬한다. 그 후 time 변수에는 시작시간을 저장하는데 그 시작시간보다 해당 시점의 끝나는 시간이 더 크다면 time을 그 시간대 회의시간의 시작시간으로 갱신하고 answer 에 1 추가한다.

다시 정리하면 첫 번째 time 변수는 종료시간이 가장 빠른 스케쥴의 종료시점으로, 두 번째 스케줄의 시작 시점이 첫 번째 종료시점보다 큰지 작은지를 판단하는 것이다.

그리디 알고리즘. 한동안 공부를 소홀히 했던 것 같아서 이 쪽 문제들도 자주 포스팅하겠다.

profile
블로그 이전합니다 : https://swj-techblog.vercel.app/

0개의 댓글