[백준-11000] 강의실 배정

11000번: 강의실 배정

그리디 "활동 선택 문제" 방식의 문제이다.

먼저 시간복잡도부터 살펴보면 1초의 제한시간에 input 의 길이가 20만이다. 따라서 제곱의 복잡도를 가지게 되면 터진다는 걸 알 수 있다.

이 점에 착안해 각 프로세스를 돌면서 log(n) 의 탐색 복잡도 로직으로 같이 이어서 들을 강의를 체킹하여 문제를 풀기로 하였다.

로직은 다음과 같다.

1. 각 프로세스를 "시간 순 → 짧게 끝나는 순" 으로 정렬한다.
2. 정렬한 프로세스를 하나씩 돌면서 나머지 프로세스 중 바로 시작할 수 있는 프로세스를 이분탐색을 통해 찾는다. (반복)

2. 찾은 프로세스들을 모두 checking 해주고 다시 2번으로 돌아간다.

이에 대한 코드는 다음과 같다.

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <tuple>
#include <string>
#include <string.h>
#include <stack>
#include <set>
#include <map>


using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int check[200001];
bool compare(pii a, pii b) {
	if (a.first == b.first) {
		return a.second < b.second;
	}
	else {
		return a.first < b.first;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n, a, b;
	cin >> n;
	vector<pii> cls;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		cls.push_back({ a,b });
	}
	sort(cls.begin(), cls.end(), compare);

	vector<int> idx;
	for (int i = 0; i < cls.size(); i++)
		idx.push_back(cls[i].first);

	int res = 0;
	for (int i = 0; i < cls.size(); i++) {
		if (check[i] != 0) continue;
		else check[i] = 1;

		int cx = cls[i].first;
		int cy = cls[i].second;

		while (1) {
			// 제일 맞는 놈 바로 체킹 -> log(n)
			int id = lower_bound(idx.begin(), idx.end(), cy) - idx.begin();
			while (check[id] != 0) 
				id += 1;
			if (id > cls.size() - 1 || cls[id].first < cy) 
				break;
			check[id] = 1;
			cy = cls[id].second;
		}
		res += 1;
	}
	cout << res;
	return 0;
}