forked from kamyu104/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
maximum-number-of-achievable-transfer-requests.cpp
90 lines (84 loc) · 2.73 KB
/
maximum-number-of-achievable-transfer-requests.cpp
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
// Time: O((n + r) * 2^r)
// Space: O(n + r)
// early return solution
class Solution {
public:
int maximumRequests(int n, vector<vector<int>>& requests) {
const auto& check =
[&n, &requests](const auto& idx) {
vector<int> change(n);
for (const auto& i : idx) {
--change[requests[i][0]];
++change[requests[i][1]];
}
return all_of(cbegin(change), cend(change),
[](const auto& x) {
return x == 0;
});
};
for (int k = size(requests); k > 0; --k) {
if (combinations(size(requests), k, check)) {
return k; // early return
}
}
return 0;
}
private:
bool combinations(int n, int k, const function<bool (const vector<int>&)>& callback) {
static const auto& next_pos =
[](const auto& n, const auto& k, const auto& idxs) {
int i = k - 1;
for (; i >= 0; --i) {
if (idxs[i] != i + n - k) {
break;
}
}
return i;
};
vector<int> idxs(k);
iota(begin(idxs), end(idxs), 0);
if (callback(idxs)) {
return true;
}
for (int i; (i = next_pos(n, k, idxs)) >= 0;) {
++idxs[i];
for (int j = i + 1; j < k; ++j) {
idxs[j] = idxs[j - 1] + 1;
}
if (callback(idxs)) {
return true;
}
}
return false;
}
};
// Time: O((n + r) * 2^r)
// Space: O(n + r)
// full search solution (much slower)
class Solution2 {
public:
int maximumRequests(int n, vector<vector<int>>& requests) {
const auto& evaluate =
[&n, &requests](const auto& mask) {
vector<int> change(n);
int count = 0;
for (int i = 0, base = 1; i < size(requests); ++i, base <<= 1) {
if (base & mask) {
--change[requests[i][0]];
++change[requests[i][1]];
++count;
}
}
return all_of(cbegin(change), cend(change),
[](const auto& x) {
return x == 0;
}) ? count : 0;
};
const auto& total = 1 << size(requests);
int result = 0;
for (int mask = 0; mask < total; ++mask) {
result = max(result, evaluate(mask));
}
return result;
}
};