백준 1931

백준 1931

문제는 여러 회의 시간이 주어지고, 최대한 많은 회의가 진행할 수 있는 최대 회의의 수를 구하는 것이다. 이 때, 회의 시간이 시작 시간과 종료 시간이 같을 수도 있다.
ex)
3
1 1
1 2
2 2
ans = 3
이 문제의 핵심은 시작 시간을 기준으로 정렬해서 푸는 것이 아니라, 종료 시간을 기준으로 오름차순으로 정렬을 하고, 종료 시간이 가장 늦은 회의를 시작으로 먼저 하나씩 회의를 카운팅하는 것이 핵심이다. 주어진 n이 100,000개이기 때문에 최소 O(nlogn)의 시간 복잡도를 가져야 한다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n;
vector<pair<int,int>> v;
int main() {

	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;

	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		v.push_back({ b,a });
	}
	
	sort(v.begin(), v.end());
	
	int cnt = 1;
	int time = v[0].first;

	for (int i = 1; i < n; i++) {
		if (time <= v[i].second) {
			time = v[i].first;
			cnt++;
		}
	}
	cout << cnt;

	return 0;
}

처음에는 너무 복잡하게 생각해서 투포인터 느낌으로 회의 하나를 인덱스로 생각해서 투포인터로 풀려고 했다. 투포인터로 풀다보니 깔끔하게 풀이가 나오지 않았고, 처음 시간을 잡고 비교하면서 푸니 깔끔하게 나왔다. 쉬운 문제에 시간을 너무 씀.. 반성하자...