11000번: 강의실 배정
그리디 "활동 선택 문제" 방식의 문제이다.
먼저 시간복잡도부터 살펴보면 1초의 제한시간에 input 의 길이가 20만이다. 따라서 제곱의 복잡도를 가지게 되면 터진다는 걸 알 수 있다.
이 점에 착안해 각 프로세스를 돌면서 log(n) 의 탐색 복잡도 로직으로 같이 이어서 들을 강의를 체킹하여 문제를 풀기로 하였다.
로직은 다음과 같다.
- 각 프로세스를 "시간 순 → 짧게 끝나는 순" 으로 정렬한다.
- 정렬한 프로세스를 하나씩 돌면서 나머지 프로세스 중 바로 시작할 수 있는 프로세스를 이분탐색을 통해 찾는다. (반복)
- 찾은 프로세스들을 모두 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;
}'책장 > 알고리즘' 카테고리의 다른 글
| [백준-1918] 후위 표기식 (1) | 2021.08.11 |
|---|---|
| [백준-20040] 사이클 게임 (0) | 2021.08.11 |
| [프로그래머스] 큰수만들기 (0) | 2021.08.11 |
| [백준-1082] 방번호 (0) | 2021.08.10 |
