1.4.6 Deadline Scheduling

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
91
92
93
94

/*

Schedules unit-time jobs with deadlines and profits to maximize total profit. Each job takes one
time slot and must be scheduled at or before its deadline. The greedy algorithm processes jobs in
decreasing profit order and places each chosen job in the latest available slot before its deadline.

The latest-slot choice is safe because it uses the current high-profit job while leaving earlier
slots available for jobs with tighter deadlines. A disjoint-set forest over time slots makes this
efficient: `find(t)` returns the latest still-free slot at or before `t`, and occupying slot `t`
links it to the next candidate slot `t - 1`.

- `select_deadline_jobs(jobs)` returns a pair (`profit`, `slot`) containing that maximum profit and
  `slot[i]`, the assigned time slot of input job `i`, or $-1$ if that job is not selected, for a
  vector of `Job` with fields `deadline` and `profit`. Deadlines are positive integers, and assigned
  slots are numbered starting from $1$. Jobs with nonpositive profit are not selected.

Overflow warning: The total profit must fit in `int64_t`.

Time Complexity:
- O(n log n) per call due to sorting, with near-constant disjoint-set operations.

Space Complexity:
- O(n) auxiliary and O(n) for the returned slot assignment.

*/

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <numeric>
#include <utility>
#include <vector>

struct Job {
  int deadline;
  int64_t profit;
};

class SlotDSU {
  std::vector<int> root;

 public:
  explicit SlotDSU(int n) : root(n + 1) { std::iota(root.begin(), root.end(), 0); }

  int find(int u) { return root[u] == u ? u : root[u] = find(root[u]); }
  void occupy(int u) { root[u] = find(u - 1); }
};

std::pair<int64_t, std::vector<int>> select_deadline_jobs(const std::vector<Job> &jobs) {
  for (const auto &job : jobs) {
    assert(job.deadline > 0);
  }
  int n = static_cast<int>(jobs.size());
  std::vector<int> order(n);
  std::iota(order.begin(), order.end(), 0);
  std::sort(order.begin(), order.end(), [&](int i, int j) {
    return jobs[i].profit != jobs[j].profit ? jobs[i].profit > jobs[j].profit
                                            : jobs[i].deadline < jobs[j].deadline;
  });
  int max_deadline = 0;
  for (const auto &j : jobs) {
    max_deadline = std::max(max_deadline, j.deadline);
  }
  max_deadline = std::min(max_deadline, n);
  SlotDSU slots(max_deadline);
  std::vector<int> assigned(n, -1);
  int64_t res = 0;
  for (int i : order) {
    if (jobs[i].profit <= 0) {
      continue;
    }
    int slot = slots.find(std::min(jobs[i].deadline, max_deadline));
    if (slot > 0) {
      res += jobs[i].profit;  // Overflow warning.
      assigned[i] = slot;
      slots.occupy(slot);
    }
  }
  return {res, assigned};
}

/*** Example Usage ***/

#include <cassert>
using namespace std;

int main() {
  vector<Job> jobs{{2, 100}, {1, 19}, {2, 27}, {1, 25}, {3, 15}};
  auto [profit, slot] = select_deadline_jobs(jobs);
  // Jobs 0, 2, 4 fill slots 2, 1, 3 for total profit 100 + 27 + 15.
  assert(profit == 142);
  assert((slot == vector<int>{2, -1, 1, -1, 3}));
  return 0;
}