Backjoon_그리디_1931

내가 풀 때까지만 해도 정답률이 29프로였는데 너무 틀려서 그런지 28프로로 떨어졌다.

실패를 많이 거쳤는데 접근 방식을 잘못 잡았었다.

INPUT
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

OUTPUT
12 14
5 7
3 5
8 11
1 4
8 12
6 10
5 9
3 8
0 6

이런식으로 회의시간이 짧은 것 순 중에 종료시각이 큰 것을 기준으로 정렬을 하려고 했다.
( 힌트에 (1,4), (5,7), (8,11), (12,14) 를 이용이 없었다면 이러지 않았을 것이다. 한 회의의 시작시간과 다른회의의 시작시간이 겹치지 않는 것이 힌트인 줄로만 착각했다. )

이 문제에 대한 해결책은 무조건 종료시각이 빠른 순으로 정렬하는데 중요한 점은 종료시각이 같을 경우 시작시간이 작은 순서대로 정렬하여야 하는 점이다.
( (3,3),(2,3),(3,3) 의 입력의 경우 최적해가 (2,3),(3,3) 으로 나와야 하기 때문이다. )

이 문제의 경우 N<=100,000 이므로 O(N^2) 의 경우를 피해야 한다.
즉 입력받은 값들을 정렬하는 시간이 O(NlogN)을 가져야 한다는 말이다.
sort() 메서드의 경우 NlogN 시간으로 정렬해주므로 따로 신경쓴 것은 없다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool compare(const pair<int, int>& p1, const pair<int, int>& p2)
{
	if (p1.second == p2.second)
	{
		return p1.first < p2.first;
	}
	return p1.second < p2.second;
}

int main()
{
	int N, T;
	vector<int> checked;
	int count = 0;
	cin >> N;
	T = N;
	vector<pair<int, int> > v;
	while (T--)
	{
		int a, b;
		cin >> a >> b;
		v.push_back(make_pair(a, b));
	}
	
	sort(v.begin(), v.end(), compare);

	int min = v[0].second;
	count++;

	for (int i = 1; i < N; i++)
	{
		if (v[i].first >= min)
		{
			min = v[i].second;
			count++;
		}
	}
	cout << count;
	return 0;
}