Activity Selection & Greedy Scheduling
1. Algorithm & Complexity
The Activity Selection problem (also known as “interval scheduling maximization”) asks:
Given N activities, each with a start time si and finish time fi,
select the maximum‐size subset of non‐overlapping activities.
Greedy solution:
- Sort all activities by increasing finish time (
fi). - Initialize
last_end = –∞, and an empty listS. - For each activity i in sorted order:
- if
si ≥ last_end, select it: append i toS, and setlast_end = fi.
- if
- Return
S(the maximum set).
Time Complexity
– Sorting N activities by finish time: O(N log N)
– Single scan through sorted list: O(N)
Total: O(N log N)
Memory Complexity
– Store the list of activities: O(N)
– Sorting uses O(N) auxiliary (or O(log N) for in‐place heapsort)
Total: O(N)
2. Easy Problems on Codeforces
2.1 – Codeforces #545C “Woodcutters”
You have N trees in a row, tree i at position i has height hi. You may cut each tree so it falls left or right (or not cut it), but it must not hit another tree. Maximize the number of cut trees.
Input: 5 1 2 5 10 10 Output: 3
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n; cin >> n;
vector<long long> x(n), h(n);
for (int i = 0; i < n; ++i) cin >> x[i] >> h[i];
if (n <= 2) { cout << n << "\n"; return 0; }
int ans = 2; // cut first left and last right
long long last = x[0]; // rightmost occupied point
for (int i = 1; i < n - 1; ++i) {
if (x[i] - h[i] > last) {
// cut left
ans++;
last = x[i];
}
else if (x[i] + h[i] < x[i+1]) {
// cut right
ans++;
last = x[i] + h[i];
}
else {
// leave standing
last = x[i];
}
}
cout << ans << "\n";
return 0;
}
2.2 – Codeforces #701A “Cards”
You have N cards, each shows a number. You may remove a card if its number is strictly between the numbers on two neighboring cards. Maximize the number of remaining cards. (This reduces to choosing a subsequence with no “three in a row” violation – a simple greedy scan.)
Input: 5 1 4 2 3 5 Output: 4
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n; cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
vector<int> keep;
keep.push_back(a[0]);
for (int i = 1; i < n - 1; ++i) {
if ((a[i] > a[i-1] && a[i] < a[i+1]) ||
(a[i] < a[i-1] && a[i] > a[i+1])) {
// removable: skip
} else {
keep.push_back(a[i]);
}
}
keep.push_back(a[n-1]);
cout << keep.size() << "\n";
return 0;
}
3. Intermediate Problems on Codeforces
3.1 – Codeforces #545C Variant (“Multiple Woodcutters”)
Given the same setting as 545C, but you have K different saws and may fell up to K trees at once in parallel. You still sort by position and greedily assign saws in finish‐time order (right‐fall times).
Input: 5 2 1 2 5 10 10 Output: 4
#include <iostream>
#include <vector>>
#include <set>>
using namespace std;
int main() {
int n, K; cin >> n >> K;
vector<pair<long long,long long>> trees(n);
for (int i = 0; i < n; ++i) {
long long x, h; cin >> x >> h;
trees[i] = {x, h};
}
// always cut first tree to the left
multiset<long long> saws;
for (int i = 0; i < K; ++i) saws.insert(LLONG_MIN);
int ans = 0;
for (auto &t : trees) {
long long x = t.first, h = t.second;
// try left fall
auto it = prev(saws.end());
if (*it <= x - h) {
saws.erase(it);
saws.insert(x);
ans++;
}
// else try right fall: assign finish = x+h
else if (*saws.begin() <= x) {
saws.erase(saws.begin());
saws.insert(x + h);
ans++;
}
}
cout << ans << "\n";
return 0;
}
3.2 – Codeforces #437B “The Child and Sequence”
Given an array of N values and Q queries [L,R], for each query select the maximum‐size subset of non‐overlapping segments where each segment’s sum ≤ S. You can treat each valid subarray as an “activity” [start,end], sort by end, and greedily pick.
Input: 5 2 5 1 2 3 1 2 1 3 2 5 Output: 1 2
#include <iostream>>
#include <vector>>
#include <algorithm>>
using namespace std;
// Precompute all “good” segments with sum ≤ S, then sort by end.
// For each query, binary‐search on sorted list and greedy‐count.
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, Q;
long long S;
cin >> N >> Q >> S;
vector<long long> a(N+1), pref(N+1);
for (int i = 1; i <= N; ++i) {
cin >> a[i];
pref[i] = pref[i-1] + a[i];
}
// collect all valid segments [i,j]
vector<pair<,int>> segs;
for (int i = 1; i <= N; ++i) {
for (int j = i; j <= N; ++j) {
if (pref[j] - pref[i-1] <= S)
segs.push_back({j,i});
}
}
sort(segs.begin(), segs.end()); // by end then start
while (Q--) {
int L, R; cin >> L >> R;
int last = L-1, cnt = 0;
for (auto &p : segs) {
int end = p.first, start = p.second;
if (start >= last+1 && end <= R) {
cnt++;
last = end;
}
}
cout << cnt << "\n";
}
return 0;
}
4. Hard Problem on Codeforces
4.1 – Weighted Interval Scheduling (CF‐style “Projects”)
Given N projects each with [start, end] and weight Wi, choose non‐overlapping set maximizing total weight.
This is the weighted version and requires DP + binary search in O(N log N).
Input: 4 1 3 10 2 5 20 4 6 30 6 7 25 Output: 55 (choose intervals [1–3] with w=10 and [4–6] with w=30 and [6–7] w=25)
#include <iostream>>
#include <vector>>
#include <algorithm>>
using namespace std;
struct P { int s,e; long long w; };
int main(){
int N; cin >> N;
vector<P> a(N+1);
for(int i=1;i<=N;i++) cin>>a[i].s>>a[i].e>>a[i].w;
sort(a.begin()+1, a.end(), [](auto &A, auto &B){
return A.e<B.e;
});
vector<long long> dp(N+1);
vector<int> ends(N+1);
for(int i=1;i<=N;i++) ends[i]=a[i].e;
for(int i=1;i<=N;i++){
// find last j < i with end ≤ a[i].s
int j = int(upper_bound(ends.begin()+1, ends.begin()+i, a[i].s) - ends.begin()) - 1;
dp[i] = max(dp[i-1], dp[j] + a[i].w);
}
cout<<dp[N]<<"\n";
return 0;
}
All examples above use the same greedy or DP+binary‐search blueprint:
- Sort activities by finish-time.
- Greedily pick compatible ones (unweighted case) or
- Use DP with binary search for weighted case.