Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Greedy

Job Sequencing

Medium · Greedy · Asked at Amazon, Microsoft, Flipkart, Accenture

Each job takes one unit of time and has a deadline and a profit; you earn the profit only if the job finishes by its deadline. Only one job runs at a time, starting at time 0. Print the maximum number of jobs done and the maximum total profit — the count is the number of jobs in a schedule with maximum profit (choose the schedule greedily by profit).

Input

First line: n. Next n lines: deadline profit.

Output

Two integers: the number of jobs done and the total profit.

Constraints

Sort jobs by profit (highest first). Put each job in the latest free time slot not after its deadline; skip it if none is free. A DSU over slots makes finding the slot fast.

Example 1

Input

4
4 20
1 10
1 40
1 30

Output

2 60

Example 2

Input

5
2 100
1 19
2 27
1 25
1 15

Output

2 127

Hints

  1. Consider the most profitable jobs first.
  2. Schedule each job as late as possible (the latest free slot ≤ its deadline), which keeps earlier slots free for jobs with earlier deadlines.

Approach

Sort jobs by profit descending. For each job, look for a free slot t from its deadline down to 1; if found, occupy it and add the profit. A union–find over slots (find(t) = latest free slot ≤ t, and occupying t links it to t − 1) turns the search into near O(1), giving O(n log n) overall.

Complexity: O(n log n) time · O(n) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

vector<int> par;
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> jobs(n); // (profit, deadline)
    for (auto &j : jobs) cin >> j.second >> j.first;
    sort(jobs.rbegin(), jobs.rend());
    par.resize(n + 1);
    iota(par.begin(), par.end(), 0);
    long long count = 0, profit = 0;
    for (auto &j : jobs) {
        int slot = find(min(j.second, n));
        if (slot > 0) {
            par[slot] = slot - 1;
            count++;
            profit += j.first;
        }
    }
    cout << count << " " << profit << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n = data[0]
jobs = sorted(((data[2 + 2 * i], data[1 + 2 * i]) for i in range(n)), reverse=True)
par = list(range(n + 1))


def find(x):
    while par[x] != x:
        par[x] = par[par[x]]
        x = par[x]
    return x


count = profit = 0
for p, d in jobs:
    slot = find(min(d, n))
    if slot > 0:
        par[slot] = slot - 1
        count += 1
        profit += p
print(count, profit)

Java solution

import java.util.*;

public class Main {
    static int[] par;

    static int find(int x) {
        while (par[x] != x) {
            par[x] = par[par[x]];
            x = par[x];
        }
        return x;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] jobs = new int[n][2];
        for (int i = 0; i < n; i++) {
            jobs[i][1] = sc.nextInt();
            jobs[i][0] = sc.nextInt();
        }
        Arrays.sort(jobs, (a, b) -> b[0] - a[0]);
        par = new int[n + 1];
        for (int i = 0; i <= n; i++) par[i] = i;
        long count = 0, profit = 0;
        for (int[] j : jobs) {
            int slot = find(Math.min(j[1], n));
            if (slot > 0) {
                par[slot] = slot - 1;
                count++;
                profit += j[0];
            }
        }
        System.out.println(count + " " + profit);
    }
}

Solve Job Sequencing online · All practice problems