알고리즘
a, b에서 b의 순서대로 정렬
1 2
1 1
이런식으로 입력이 들어오면, 1 2에서 1에 넣고 1 1에선 넣을 수가 없기 때문에.
정렬된 (a, b)를 앞에서부터 검사하는데, a에서 b까지 1씩 증가하면서 가능하면 책을 배정하고, b까지 검사했는데도 남아있는 책이없으면 패스한다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <list>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
list<pair<int, int>> l;
vector<pair<int, int>> v;
bool card[1001];
int main() {
int tc;
cin >> tc;
while (tc--) {
int n, m, ans = 0, a, b;
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> a >> b;
v.push_back({ b, a });
}
sort(v.begin(), v.end());
for (int i = 0; i < v.size(); i++) {
l.push_back({ v[i].second, v[i].first });
}
v.clear();
auto iter = l.begin();
while (iter != l.end()) {
int f = iter->first, s = iter->second;
if (!card[f]) {
card[f] = true;
ans++;
iter = l.erase(iter);
}
else {
if (f + 1 > s)
iter = l.erase(iter);
else {
bool check = true;
for (int i = f + 1; i <= s; i++) {
if (!card[i]) {
card[i] = true;
ans++;
iter = l.erase(iter);
check = false;
break;
}
}
if (check) {
iter = l.erase(iter);
}
}
}
}
cout << ans << endl;
memset(card, 0, sizeof(card));
}
}