123 lines
4.4 KiB
Python
123 lines
4.4 KiB
Python
"""Weighted Interval Scheduling via dynamic programming.
|
|
|
|
Given intervals (start, end, weight), choose a subset of mutually
|
|
non-overlapping intervals maximizing total weight. Intervals overlap when
|
|
their time ranges intersect with positive length; touching endpoints
|
|
([a,b] and [b,c]) are allowed to coexist.
|
|
|
|
Algorithm:
|
|
sort intervals by end time
|
|
p[i] = largest index j < i with end_j <= start_i (predecessor)
|
|
OPT[i] = max(OPT[i-1], weight_i + OPT[p[i]])
|
|
answer OPT[n]
|
|
|
|
Predecessor search uses binary search on sorted end-times: O(n log n).
|
|
"""
|
|
from __future__ import annotations
|
|
|
|
import bisect
|
|
from typing import List, Tuple
|
|
|
|
|
|
Interval = Tuple[int, int, int] # (start, end, weight)
|
|
|
|
|
|
def weighted_interval_scheduling(intervals: List[Interval]) -> int:
|
|
"""Maximum total weight of a mutually compatible subset.
|
|
|
|
Compatibility is the docstring's rule -- an intersection of positive
|
|
length is the only thing that blocks a pair -- so a zero-length
|
|
interval (start == end) overlaps nothing, not even another zero-length
|
|
interval at the same point. Every zero-length interval with positive
|
|
weight can therefore be taken unconditionally and is added to the
|
|
optimum instead of entering the recurrence, which can only express
|
|
predecessor relations between positive-length ranges.
|
|
|
|
A reversed interval (end < start) is not an interval under this rule
|
|
(its range is empty in the other direction) and is rejected rather
|
|
than silently scheduled.
|
|
"""
|
|
if not intervals:
|
|
return 0
|
|
free = 0
|
|
admissible: List[Interval] = []
|
|
for s, e, w in intervals:
|
|
if e < s:
|
|
raise ValueError(
|
|
"invalid interval (start %r > end %r): %r" % (s, e, (s, e, w))
|
|
)
|
|
if e == s:
|
|
if w > 0:
|
|
free += w
|
|
else:
|
|
admissible.append((s, e, w))
|
|
if not admissible:
|
|
return free
|
|
# sort by end time; keep original weights
|
|
iv = sorted(admissible, key=lambda x: x[1])
|
|
n = len(iv)
|
|
ends = [iv[i][1] for i in range(n)]
|
|
# dp[i] = best using first i intervals (1-indexed); dp[0]=0
|
|
dp = [0] * (n + 1)
|
|
for i in range(1, n + 1):
|
|
s, e, w = iv[i - 1]
|
|
# predecessor: largest j (0..i-1) with ends[j-1] <= s -> index j in 1-based terms
|
|
# search in ends[0:i-1]
|
|
j = bisect.bisect_right(ends, s, 0, i - 1) # count of ends <= s among first i-1
|
|
# j is count => predecessor dp index j
|
|
take = w + dp[j]
|
|
skip = dp[i - 1]
|
|
dp[i] = take if take > skip else skip
|
|
return free + dp[n]
|
|
|
|
|
|
def brute_force(intervals: List[Interval]) -> int:
|
|
"""Exhaustive enumeration for verification on small inputs.
|
|
|
|
Applies the positive-length overlap rule directly and does no input
|
|
validation, so it is only a reference for inputs the scheduler accepts:
|
|
reversed intervals (end < start) are rejected there and are outside
|
|
this function's contract.
|
|
"""
|
|
n = len(intervals)
|
|
best = 0
|
|
for mask in range(1 << n):
|
|
chosen = [intervals[k] for k in range(n) if mask & (1 << k)]
|
|
ok = True
|
|
for a in range(len(chosen)):
|
|
for b in range(a + 1, len(chosen)):
|
|
# overlap with positive length
|
|
s1, e1, _ = chosen[a]
|
|
s2, e2, _ = chosen[b]
|
|
lo = max(s1, s2)
|
|
hi = min(e1, e2)
|
|
if hi - lo > 0:
|
|
ok = False
|
|
break
|
|
if not ok:
|
|
break
|
|
if ok:
|
|
best = max(best, sum(w for _, _, w in chosen))
|
|
return best
|
|
|
|
|
|
if __name__ == "__main__":
|
|
# self-test with randomized comparison
|
|
import random
|
|
random.seed(42)
|
|
for trial in range(4000):
|
|
n = random.randint(0, 8)
|
|
ivs = []
|
|
for _ in range(n):
|
|
s = random.randint(0, 6)
|
|
length = random.randint(0, 4) # 0 -> zero-length, admissible
|
|
e = s + length
|
|
w = random.randint(-3, 9) # signed weights: negatives must be dropped
|
|
ivs.append((s, e, w))
|
|
a = weighted_interval_scheduling(ivs)
|
|
b = brute_force(ivs)
|
|
if a != b:
|
|
raise SystemExit(f"MISMATCH trial={trial} got={a} exp={b} ivs={ivs}")
|
|
print("OK: 4000 randomized trials passed (zero-length and signed weights included)")
|
|
print("example:", weighted_interval_scheduling([(1, 3, 5), (2, 5, 6), (4, 6, 5), (6, 7, 4)]))
|