백준 1931번(그리디)

백준 1931번(그리디)

처음에 낸 아이디어는 시작 시간, 종료시간을 pair를 사용해서 묶어서 벡터에 저장후 시작 시간으로 오름차순으로 정렬 한뒤 문제에 맞게 요소들을 고르고 갯수를 증가시키는 방식이었습니다. 하지만 시간초과가 났고, 또한 간과한 문제점도 있었습니다. 일단 for를 두번 사용해서 시간초과가 났을 뿐아니라 이 방식은 일찍 시작했지만 종료 시간이 늦을 경우에는 최대 회의 갯수를 얻을 수 없었습니다. 그래서 종료 시간을 기준으로 오름차순으로 정렬하여 위 문제를 해결하였습니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(pair<int, int> a, pair<int, int> b) { // 정렬 기준 
	if (a.second == b.second) { // 종료 시간이 같을 경우 시작 시간으로 오름차순
		return a.first < b.first;
	}
	else {
		return a.second < b.second; // 기본적으로 종료 시간으로 오름차순
	}
}

int main() {
	int n = 0;
	int start = 0;
	int end = 0;
	int num = 0;
	vector<pair<int, int>> pairTime;

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> start;
		cin >> end;
		pairTime.push_back(pair<int, int>(start, end));
	}

	sort(pairTime.begin(), pairTime.end(), compare);

	end = pairTime[0].second;
	num++;

	for (int i = 1; i < n; i++) {
		if (pairTime[i].first >= end) {
			num++;
			end = pairTime[i].second;
		}
	}

	cout << num;

	return 0;
}