1.4.3 Weighted Interval 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
95
96
97
98
99
100
101
102

/*

Selects a maximum-weight subset of non-overlapping intervals using dynamic programming and binary
search. Unlike unweighted interval scheduling, the earliest finish-time greedy choice is not
sufficient when intervals have weights. With intervals sorted by finish time, the best total for the
first $i$ intervals either skips interval $i$ or adds its weight to the best total over intervals
finishing no later than its start, with that predecessor located by binary search.

Intervals are represented as half-open ranges $[`start`, `finish`)$, so two intervals are compatible
if the next interval's `start` is at least the previous interval's `finish`.

- `select_weighted_intervals(intervals)` returns a pair (`weight`, `selected`) containing that
  maximum weight and the selected intervals as original input indices in execution order, from an
  input vector of `WeightedInterval` with fields `start`, `finish`, and `weight`. `dp[i]` stores the
  best answer using the first `i` intervals after sorting by finish time. Each interval must satisfy
  `start` < `finish`. The empty subset is allowed, so nonpositive weights need not be selected.

Overflow warning: Accumulated weights must fit in `int64_t`.

Time Complexity:
- O(n log n) per call due to sorting and binary searching compatible intervals.

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

*/

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

struct WeightedInterval {
  int start, finish;
  int64_t weight;
};

std::pair<int64_t, std::vector<int>> select_weighted_intervals(
    const std::vector<WeightedInterval> &intervals
) {
  for (const auto &iv : intervals) {
    assert(iv.start < iv.finish);
  }
  int n = static_cast<int>(intervals.size());
  std::vector<int> order(n), finish(n), prev(n);
  std::iota(order.begin(), order.end(), 0);
  std::sort(order.begin(), order.end(), [&](int i, int j) {
    return intervals[i].finish != intervals[j].finish ? intervals[i].finish < intervals[j].finish
                                                      : intervals[i].start < intervals[j].start;
  });
  for (int i = 0; i < n; i++) {
    finish[i] = intervals[order[i]].finish;
  }
  std::vector<int64_t> dp(n + 1);
  std::vector<char> take(n + 1);
  for (int i = 1; i <= n; i++) {
    int j =
        std::upper_bound(finish.begin(), finish.begin() + i - 1, intervals[order[i - 1]].start) -
        finish.begin();
    prev[i - 1] = j;
    int64_t candidate = dp[j] + intervals[order[i - 1]].weight;  // Overflow warning.
    if (dp[i - 1] < candidate) {
      dp[i] = candidate;
      take[i] = true;
    } else {
      dp[i] = dp[i - 1];
    }
  }
  // Optional: reconstruct one optimal subset of intervals.
  std::vector<int> selected;
  for (int i = n; i > 0;) {
    if (take[i]) {
      selected.push_back(order[i - 1]);
      i = prev[i - 1];
    } else {
      i--;
    }
  }
  std::reverse(selected.begin(), selected.end());
  return {dp[n], selected};
}

/*** Example Usage ***/

#include <cassert>
using namespace std;

int main() {
  vector<WeightedInterval> intervals{{1, 3, 5}, {2, 5, 6}, {4, 6, 5}, {6, 7, 4}, {5, 8, 11}};
  auto [weight, selected] = select_weighted_intervals(intervals);
  // Taking ids 1 and 4 beats the earliest-finish unweighted-looking choices.
  assert(weight == 17);
  assert((selected == vector<int>{1, 4}));

  vector<WeightedInterval> touching{{0, 2, 5}, {2, 4, 6}, {1, 3, 7}};
  auto [touching_weight, touching_selected] = select_weighted_intervals(touching);
  assert(touching_weight == 11);
  assert((touching_selected == vector<int>{0, 1}));
  return 0;
}