Job Sequencing & Scheduling Algorithms

1. Algorithm & Complexity

The classic Job Sequencing with Deadlines problem is: Given N jobs, each with a deadline and a profit, schedule at most one job per time slot so as to maximize total profit (each job takes unit time). The standard greedy solution:

1. Sort all jobs in descending order of profit.
2. Create an array slot[1…maxDeadline], initialized to –1 (empty).
3. For each job in sorted order:
   • Try to schedule it in the latest free slot ≤ its deadline (scan from d down to 1).
   • If you find an empty slot, assign the job there and add its profit.
4. Remaining slots stay empty.

Time Complexity

Let D = maximum deadline among all jobs.

• Sorting takes O(N log N).
• For each of N jobs, we scan up to D slots → O(N·D).

Total: O(N log N + N·D). If D = O(N), this is O(N²).

Memory Complexity

• Store N jobs → O(N).
• Slot array of size D → O(D).

Total: O(N + D).

---

2. Easy Examples

2.1 – Codeforces 1203F1 “Complete Projects (easy version)”

Given N projects, each with a duration tᵢ and a deadline dᵢ, you can do at most one project at a time. Maximize the number of completed projects. Here each project takes tᵢ time, deadline is the latest finish time.

Input:
3
3 2
1 2
2 2

Output:
2

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

int main() {
    int N;
    cin >> N;
    vector<pair<,int>> projects(N);
    for (int i = 0; i < N; i++)
        cin >> projects[i].first >> projects[i].second;
    // sort by deadline
    sort(projects.begin(), projects.end(),
         [] (auto &a, auto &b) { return a.second < b.second; });
    int currTime = 0, count = 0;
    for (auto &p : projects) {
        if (currTime + p.first <= p.second) {
            currTime += p.first;
            count++;
        }
    }
    cout << count << "\n";
    return 0;
}

2.2 – Codeforces 1592E “Tasks and Deadlines”

Given N tasks with duration tᵢ and deadline dᵢ, you must perform all tasks in some order. Compute the total “lateness penalty” = ∑|finishᵢ − dᵢ|. Greedy: sort by duration ascending (shortest‐processing‐time first).

Input:
3
3 5
1 2
2 4

Output:
3

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

int main() {
    int N; 
    cin >> N;
    vector<pair<,int>> tasks(N);
    for (int i = 0; i < N; i++)
        cin >> tasks[i].first >> tasks[i].second;
    // Sort by duration
    sort(tasks.begin(), tasks.end(),
         [] (auto &a, auto &b) { return a.first < b.first; });
    long long time = 0, penalty = 0;
    for (auto &t : tasks) {
        time += t.first;
        penalty += llabs(time - t.second);
    }
    cout << penalty << "\n";
    return 0;
}

---

3. Intermediate Examples

3.1 – Codeforces 1203F2 “Complete Projects (hard version)”

Same as F1, but N ≤ 2·10⁵, durations and deadlines large. Use a max‐heap to drop the longest project when current time exceeds deadline.

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

Output:
4

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

int main(){
    int N; 
    cin >> N;
    vector<pair<,int>> proj(N);
    for(int i=0;i<N;i++) cin >> proj[i].first >> proj[i].second;
    sort(proj.begin(), proj.end(),
         [] (auto &a, auto &b){ return a.second < b.second; });
    priority_queue<int> pq;
    long long time = 0;
    for (auto &p : proj) {
        time += p.first;
        pq.push(p.first);
        if (time > p.second) {
            time -= pq.top();
            pq.pop();
        }
    }
    cout << (int)pq.size() << "\n";
    return 0;
}

3.2 – Codeforces 1635C “Schedule the Exams”

Given M exams each with a day and duration, decide if you can schedule all so no two overlap (unit‐slot scheduling). Sort by day, assign earliest possible slot.

Input:
4 3
1 2
2 1
3 1
1 1

Output:
YES

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

int main(){
    int M, D;
    cin >> M >> D;
    vector<pair<,int>> exams(M);
    for(int i=0;i<M;i++) cin >> exams[i].first >> exams[i].second;
    sort(exams.begin(), exams.end()); 
    int day = 1;
    for (auto &e : exams) {
        if (day + e.second - 1 > D || day > e.first) {
            cout << "NO\n";
            return 0;
        }
        day += e.second;
    }
    cout << "YES\n";
    return 0;
}

---

4. Hard Example

4.1 – Codeforces 1490E “Job Sequencing (classic)”

Given N jobs with deadlines and profits (unit time), maximize profit. This is the classic greedy with slot‐array approach.

Input:
5
Job1 2 100
Job2 1 19
Job3 2 27
Job4 1 25
Job5 3 15

Output:
142

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

struct Job { string id; int dl, profit; };

int main(){
    int N;
    cin >> N;
    vector<Job> jobs(N);
    int maxD = 0;
    for(int i=0;i<N;i++){
        cin >> jobs[i].id >> jobs[i].dl >> jobs[i].profit;
        maxD = max(maxD, jobs[i].dl);
    }
    sort(jobs.begin(), jobs.end(),
         [] (auto &a, auto &b){ return a.profit > b.profit; });
    vector<bool> slot(maxD+1,false);
    int total = 0;
    for (auto &j : jobs) {
        for (int t = j.dl; t > 0; --t) {
            if (!slot[t]) {
                slot[t] = true;
                total += j.profit;
                break;
            }
        }
    }
    cout << total << "\n";
    return 0;
}