문제

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

풀이

처음에 이 문제에 접근할 때는, 시작 시간을 기준으로 오름차순 정렬하고

시작 시간이 같으면 회의 시간이 짧은 것을 우선적으로 선택하는 식으로 구현하려고 했다.

그런데 시작 시간과 회의 시간을 합치면 결국 종료 시간이 된다. 즉, 이 문제는 종료 시간이 문제 풀이에서 중요한 역할을 한다.

일찍 회의를 시작하더라도 회의 시간이 길어지면, 진행 가능한 회의 개수의 최댓값을 구할 수 없기 때문이다.

따라서, 종료 시간을 기준으로 오름차순 정렬하고, 현재 회의 시작 시간이 이전 회의 종료 시간과 같거나 더 크면 모든 회의의 종료 시간, 회의의 개수를 갱신시키면 된다.

#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> pii;

// 종료 시간 기준으로 오름차순 정렬 
// 종료 시간이 같으면, 시작 시간을 기준으로 오름차순 정렬 
bool compare(pii a, pii b){
	if(a.second == b.second) return a.first < b.first; 
	return a.second < b.second;
}

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

	int N; 
	cin >> N; 

	vector<pii> meetings; 
	for(int i = 0; i < N; i++){
		int start, end;
		cin >> start >> end;
		meetings.push_back({start, end});
	}

	// 종료 시간 기준으로 오름차순 정렬
	sort(meetings.begin(), meetings.end(), compare);

	// 종료 시간이 가장 빠른 회의부터 시작 
	int prevEndTime = meetings[0].second; 
	int count = 1;

	for(int i = 1; i < meetings.size(); i++){
		// 현재 회의의 시작 시간 >= 이전 회의의 종료 시간 
		if(meetings[i].first >= prevEndTime){
			prevEndTime = meetings[i].second; 
			count++; 
		}
	}

	cout << count; 
	
  	return 0;
}

회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

종료 시간이 같을 때 시작 시간을 기준으로 따로 정렬해주지 않으면, 위의 조건과 관련된 테스트 케이스에서 예외가 발생할 수도 있다.

ex) (1,3) (8,8) (4,8)

(1,3) 이후에 (8,8)을 선택해버리면 count = 2

근데 실제 정답은 (1,3) (4,8) (8,8) 즉, count = 3

따라서 종료 시간이 같을 때는 시작 시간을 기준으로 정렬해줘야 한다!