[Baekjoon/백준] 1931번: 회의실 배정(C/C++)

단계별로 풀어보기 16단계(그리디 알고리즘) 2번 문제

https://www.acmicpc.net/step/33

그리디 알고리즘 단계

---

백준 1931번: 회의실 배정

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

1931번: 회의실 배정

---

문제 설명

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

---

입력과 출력

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

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

---

접근 방법

이번 문제는 회의 개수 N을 입력 받고, 이후 N개의 줄에 걸쳐서 각 회의 시작 시간과 종료 시간을 입력받아서 회의 시간이 겹치지 않아서 사용할 수 있는 회의 최댓값을 출력하는 문제다.

회의 최댓값을 구할 때 시작 시간을 보게되면 예제 입력의 (0, 6)처럼 시작 시간은 빠르지만 종료 시간이 늦은 경우 예제 출력 4개 중 (1, 4)와 (5, 7)를 사용할 수 없으므로 최댓값을 구할 수 없게된다. 따라서 종료 시간을 보고 오름차순 정렬을 하면 된다. 종료 시간이 같다면 그 경우에는 시작 시간을 비교해준다. 이렇게 정렬된 시간을 이용해서 종료 시간과 같거나 큰 시작 시간이 있다면 회의 개수를 1 추가해주고, 종료 시간을 다음 종료시간으로 갱신 하는 반복문을 만들어주면 문제를 해결할 수 있다.

---

코드

#include <iostream>
#include <algorithm>
#define MAX 100001
using namespace std;

typedef struct conference {
	int start;
	int end;
} conference;

conference I[MAX];

bool compare(conference const &a, conference const &b) {
	if (a.end == b.end)
		return a.start < b.start;

	return a.end < b.end;
}

int main(int argc, char *argv[]) {
	int N, start, end, cur, count = 1;
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> start >> end;
		I[i] = { start, end };
	}

	sort(I, I + N, compare);

	cur = I[0].end;
	for (int i = 1; i < N; i++)
		if (I[i].start >= cur) {
			count++;
			cur = I[i].end;
		}

	cout << count << endl;

	return 0;
}

---

결과

백준 제출 결과