scheduling.weighted_interval_scheduling

Weighted Interval Scheduling Problem (Dynamic Programming with Binary Search).

Given a set of intervals (tasks/activities), each characterized by a start time, an end time, and an associated weight (value/profit), the goal is to select a subset of mutually compatible (non-overlapping) intervals that maximizes the total weight.

Unlike the unweighted interval scheduling (activity selection) problem which can be optimally solved using a greedy strategy (earliest finish time first), the weighted variant requires dynamic programming because higher-value intervals might conflict with earlier-finishing intervals.

Algorithm: 1. Sort intervals by their finish times in non-decreasing order. 2. For each interval j, compute p(j), the index of the latest compatible interval

that finishes at or before the start time of interval j. This can be found in O(log n) time using binary search (bisect_right).

  1. Compute the maximum weight subset using the recurrence: OPT(j) = max(OPT(j - 1), weight(j) + OPT(p(j)))

  2. Backtrack through the DP array to reconstruct the optimal set of intervals.

Complexity: - Time Complexity: O(n log n) due to sorting and n binary searches. - Space Complexity: O(n) for the DP table and output list.

Reference: - Kleinberg, J., & Tardos, É. (2006). Algorithm Design. Chapter 6.1:

Weighted Interval Scheduling. Addison-Wesley.

Classes

Interval

Represents a task or activity with start time, end time, and weight.

Functions

test_weighted_interval_scheduling(→ None)

Test suite for weighted interval scheduling function and Interval dataclass.

weighted_interval_scheduling(→ tuple[float, ...)

Finds the subset of compatible intervals yielding maximum total weight.

Module Contents

class scheduling.weighted_interval_scheduling.Interval

Represents a task or activity with start time, end time, and weight.

Attributes:

start: Start time of the interval. end: End time of the interval (must be strictly greater than start). weight: Value, priority, or profit of the interval (must be non-negative).

__post_init__() → None

Validate interval parameters after initialization.

>>> Interval(0, 5, 10)
Interval(start=0, end=5, weight=10)
>>> Interval(5, 2, 10)
Traceback (most recent call last):
    ...
ValueError: Start time (5) must be strictly less than end time (2).
>>> Interval(1, 5, -3)
Traceback (most recent call last):
    ...
ValueError: Weight (-3) must be non-negative.
end: float
start: float
weight: float
scheduling.weighted_interval_scheduling.test_weighted_interval_scheduling() → None

Test suite for weighted interval scheduling function and Interval dataclass.

>>> test_weighted_interval_scheduling()
scheduling.weighted_interval_scheduling.weighted_interval_scheduling(intervals: list[Interval]) → tuple[float, list[Interval]]

Finds the subset of compatible intervals yielding maximum total weight.

Args:

intervals: A list of Interval objects.

Returns:

A tuple (max_weight, selected_intervals) where: - max_weight is the maximum sum of weights achievable. - selected_intervals is the list of non-overlapping Interval objects selected.

Examples:
>>> intervals = [
...     Interval(0, 3, 3),
...     Interval(1, 5, 4),
...     Interval(4, 6, 2),
...     Interval(6, 8, 5),
... ]
>>> max_weight, selected = weighted_interval_scheduling(intervals)
>>> max_weight
10.0
>>> [(i.start, i.end, i.weight) for i in selected]
[(0, 3, 3), (4, 6, 2), (6, 8, 5)]

>>> # Classic case where greedy choice fails:
>>> intervals = [
...     Interval(1, 4, 10),
...     Interval(3, 6, 12),
...     Interval(5, 8, 10),
... ]
>>> max_weight, selected = weighted_interval_scheduling(intervals)
>>> max_weight
20.0
>>> [(i.start, i.end, i.weight) for i in selected]
[(1, 4, 10), (5, 8, 10)]

>>> # Empty input
>>> weighted_interval_scheduling([])
(0.0, [])

>>> # Single interval
>>> max_weight, selected = weighted_interval_scheduling([Interval(2, 5, 7.5)])
>>> max_weight
7.5
>>> [(i.start, i.end, i.weight) for i in selected]
[(2, 5, 7.5)]

>>> # Completely overlapping intervals: picks the highest weight
>>> overlapping = [
...     Interval(1, 10, 5),
...     Interval(2, 9, 15),
...     Interval(3, 8, 8),
... ]
>>> max_weight, selected = weighted_interval_scheduling(overlapping)
>>> max_weight
15.0
>>> [(i.start, i.end, i.weight) for i in selected]
[(2, 9, 15)]

>>> # Invalid intervals raise ValueError
>>> Interval(5, 2, 10)
Traceback (most recent call last):
    ...
ValueError: Start time (5) must be strictly less than end time (2).

>>> Interval(1, 5, -3)
Traceback (most recent call last):
    ...
ValueError: Weight (-3) must be non-negative.