문제 출처

1. 문제설명

  • N개의 회의실이 주어진다.
    • 각각은 시작시간, 끝나는시간이 있으며,
    • 어떤 회의의 시작시간과 다른 회의의 끝나는 시간은 겹칠 수 있다.
  • 주어진 시간 내에 사용할 수 있는 최대 회의의 개수를 출력하라.



2. 알고리즘 설계

  • 정렬 + 그리디 문제
  • priority queue 또는 벡터를 사용해 정렬한다.
    • 정렬 기준은 끝나는 시간으로!
  • 그리디하게 회의실을 사용하면 된다.



3. 로직

  • 정렬된 원소를 하나씩 꺼내면서 끝난 시간보다 크다면,
  • 카운팅하고, 끝난 시간을 갱신하면 된다.



4. 전체 코드

#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n; cin >> n;
	vector<pii> v(n);
	for (int i = 0; i < n; i++)
		cin >> v[i].second >> v[i].first;

	sort(v.begin(), v.end());

	int ans = 1, end = v[0].first;
	for (int i = 1; i < n; i++) {
		if (v[i].second >= end) {
			ans++;
			end = v[i].first;
		}
	}

	cout << ans;
	return 0;
}

5. 소감

  • 꿀팁
    • 이전에도 언급했지만, 우선순위 큐나, sort를 사용할 때
    • 기본 자료형 int, pair, tuple 등을 사용하면,
    • 가장 첫번째 원소를 기준으로 정렬이 우선된다.
    • pair 예시
      • {1, 2}, {2, 1}이 각각 있다면,
      • 첫 번째 원소인 1과 2를 비교하여 정렬하게 된다.
  • 위와 같은 이유로 끝나는 시간을 first로 넣어 정렬하였다.
  • 만약 구조체를 쓰는 경우에는 operator를 별도로 구현해야 하니,
    • 참 편리하다.