Interval Scheduling & Greedy Algorithms

1. Algorithm & Complexity

The classic Interval Scheduling Maximization problem is: “Given N jobs, each with a start time [si] and end time [fi], select the maximum-size subset of non‐overlapping jobs.”

The optimal greedy algorithm is:

  1. Sort all intervals by their finish times (fi) in non‐decreasing order.
  2. Initialize last_end = −∞, and an empty list of selected jobs.
  3. For each interval (s, f) in sorted order:
    • If s ≥ last_end, select this interval, and set last_end = f.
  4. Return the selected set.

Time Complexity

Sorting takes O(N log N), then the linear scan is O(N), so overall O(N log N).

Memory Complexity

We store the list of intervals and a few scalars. Total extra space is O(N).

2. Two Easy Codeforces-style Problems

2.1 Maximum Meetings (CF-X01A)

You have N meetings with start/end times. Schedule as many as possible in one room. 

Input:
5
1 4
3 5
0 6
5 7
8 9

Output:
3

Explanation: You can take meetings [1,4], [5,7], [8,9]. 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N; 
    cin >> N;
    vector<pair<int,int>> a(N);
    for (int i = 0; i < N; ++i)
        cin >> a[i].first >> a[i].second;
    sort(a.begin(), a.end(), [](auto &x, auto &y){
        return x.second < y.second;
    });
    int last_end = -1, cnt = 0;
    for (auto &intv : a) {
        if (intv.first >= last_end) {
            ++cnt;
            last_end = intv.second;
        }
    }
    cout << cnt << "\n";
    return 0;
}

2.2 Minimum Removals (CF-X02B)

Given N intervals, remove the fewest to eliminate all overlaps. 

Input:
4
1 3
2 4
3 5
6 7

Output:
1

Explanation: Remove [2,4], then remaining [1,3],[3,5],[6,7] are non-overlapping. 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N; 
    cin >> N;
    vector<pair<int,int>> a(N);
    for (int i = 0; i < N; ++i)
        cin >> a[i].first >> a[i].second;
    sort(a.begin(), a.end(), [](auto &x, auto &y){
        return x.second < y.second;
    });
    int last_end = -1, removals = 0;
    for (auto &intv : a) {
        if (intv.first < last_end) {
            ++removals;
        } else {
            last_end = intv.second;
        }
    }
    cout << removals << "\n";
    return 0;
}

3. Two Intermediate Problems

3.1 Room Assignment (CF-X10C)

Assign each of N intervals to one of the minimum number of rooms so that no two in the same room overlap. 

Input:
3
0 10
5 15
10 20

Output:
2

Explanation: Room 1: [0,10], [10,20] Room 2: [5,15] 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int main() {
    int N; 
    cin >> N;
    vector<pair<int,int>> a(N);
    for (int i = 0; i < N; ++i)
        cin >> a[i].first >> a[i].second;
    sort(a.begin(), a.end()); 
    // min‐heap of current room end‐times
    priority_queue<int, vector<int>, greater<int>> pq;
    for (auto &intv : a) {
        if (!pq.empty() && pq.top() <= intv.first) {
            pq.pop();
        }
        pq.push(intv.second);
    }
    cout << pq.size() << "\n";
    return 0;
}

3.2 Maximum Pairs of Overlaps (CF-X11D)

Given N intervals, form as many disjoint overlapping pairs as possible: each interval can be in at most one pair, and paired intervals must overlap. 

Input:
5
1 5
2 6
7 8
3 4
5 7

Output:
2

Explanation: Possible pairs: ([1,5],[2,6]) and ([5,7],[7,8]) or ([3,4],[1,5]), etc. 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N; 
    cin >> N;
    vector<pair<int,int>> a(N);
    for (int i = 0; i < N; ++i)
        cin >> a[i].first >> a[i].second;
    sort(a.begin(), a.end(), [](auto &x, auto &y){
        return x.second < y.second;
    });
    int used = 0, ans = 0;
    vector<bool> taken(N,false);
    for (int i = 0; i < N; ++i) {
        if (taken[i]) continue;
        for (int j = i+1; j < N; ++j) {
            if (!taken[j] && a[j].first < a[i].second) {
                taken[i] = taken[j] = true;
                ++ans;
                break;
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

4. One Hard Problem

4.1 Weighted Interval Scheduling (CF-X20F)

Each of N requests has start, end, weight. Find the max‐total‐weight subset of non-overlapping intervals. 

Input:
4
1 3 5
2 5 6
4 6 5
6 7 4

Output:
10

Explanation: Pick [1,3,5] + [4,6,5] = total weight 10. 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

struct Itv { int s,e; ll w; };

int main(){
    int N; 
    cin >> N;
    vector<Itv> a(N);
    for(int i=0;i<N;i++)
        cin>>a[i].s>>a[i].e>>a[i].w;
    sort(a.begin(), a.end(), [](auto &x, auto &y){
        return x.e < y.e;
    });
    // p[i] = last interval before i that doesn't overlap
    vector<int> p(N, -1);
    for(int i=0;i<N;i++){
        for(int j=i-1;j>=0;j--){
            if(a[j].e <= a[i].s){
                p[i] = j;
                break;
            }
        }
    }
    vector<ll> dp(N);
    dp[0] = a[0].w;
    for(int i=1;i<N;i++){
        ll take = a[i].w + (p[i] >= 0 ? dp[p[i]] : 0);
        dp[i] = max(dp[i-1], take);
    }
    cout << dp[N-1] << "\n";
    return 0;
}

All these problems build on the same greedy/backtracking/DP ideas:

  • Unweighted: sort by finish time → greedy → O(N log N).
  • Partitioning: sort + min-heap → O(N log N).
  • Pairs: a simple greedy match in O(N²) or optimized with two-pointer.
  • Weighted: sort + binary search to find p[i] + 1D DP → O(N²) naïve or O(N log N).