[C++] 백준(BOJ) - 1931 : 회의실 배정

01 Feb 2024 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 입력
• 출력
• 알고리즘
• 풀이
• 코드
• 평가

문제

BOJ - 1931 : 회의실 배정(링크)

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

입력

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

출력

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

알고리즘

1. 라인 스위핑
2. 그리디
3. 정렬

풀이

1. 들어오는 구간에 대한 인자 세 가지 중 어떤 것을 기준으로 정렬을 하여야 할 지 테스트케이스를 따져보기
   • 시작, 도착, 구간 길이
2. from, to 값을 담아 놓고, 도착 구간을 기준으로 정렬 된 각 케이스들 별로 라인 스위핑을 통해 조건 검증

코드

// BOJ-1931 : 회의실 배정
#include<bits/stdc++.h>
using namespace std;

int n, from, to, cnt;
vector<pair<int, int>> v;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> from >> to;
		v.push_back({ to, from });
	}

	sort(v.begin(), v.end()); 			// 도착지점 기준 정렬

	from = v[0].second;
	to = v[0].first;
	cnt = 1;

	for (int i = 1; i < n; i++)
	{
		if (to > v[i].second) continue; // 아직 방 사용 중
		to = v[i].first;				// 새로운 from, to 정의
		from = v[i].second;
		cnt++;							// 방 개수++
	}

	cout << cnt << "\n";
	return 0;
}

평가

• 구간이 나오는 문제는 한번쯤 정렬을 생각해 보기
• 그리다는 순간 순간 최적의 선택지를 골라 내는 방법