Python weighted interval scheduling: reconstruct the accepted nonoverlapping jobs

Operation contract

The job tuple contains start, end and nonnegative reward. Endpoints are half-open, so one job ending at time four is compatible with another starting at four. Sorting by end time lets a binary search locate the last compatible prefix. Each DP entry compares skipping the current job with taking it plus the best compatible prefix. Reconstruction follows those same decisions and reports original input indices. Ties deliberately skip the current job; the policy chooses one optimum without claiming every optimum is identical.

Failure and ownership boundary

The boundary accepts at most 16 jobs, exact integer fields within zero to 1000, and strictly positive duration. Negative rewards and Boolean timestamps are rejected. The supplied list is copied into indexed records and remains unchanged. Python bisect: binary position search does not make list insertion logarithmic, Python 0/1 knapsack: descending capacity prevents item reuse and Python expiry exercise: separate pending, active and expired records at exact boundaries explain the constituent contracts.

Working program

from bisect import bisect_right

def best_schedule(jobs):
    if type(jobs) is not list or len(jobs) > 16:
        raise ValueError("job capacity")
    for job in jobs:
        if type(job) is not tuple or len(job) != 3 or any(type(value) is not int or not 0 <= value <= 1000 for value in job) or job[0] >= job[1]:
            raise ValueError("job fields")
    ordered = sorted((end, start, reward, index) for index, (start, end, reward) in enumerate(jobs))
    ends = [job[0] for job in ordered]
    best, previous, take = [0], [], []
    for position, (end, start, reward, identifier) in enumerate(ordered):
        prefix = bisect_right(ends, start, 0, position)
        candidate = best[prefix] + reward
        previous.append(prefix)
        take.append(candidate > best[-1])
        best.append(max(best[-1], candidate))
    chosen = []
    position = len(ordered)
    while position:
        if take[position - 1]:
            chosen.append(ordered[position - 1][3])
            position = previous[position - 1]
        else:
            position -= 1
    return best[-1], list(reversed(chosen))

print("schedule:", best_schedule([(0, 4, 5), (1, 3, 4), (3, 5, 4), (4, 6, 5)]))
print("empty:", best_schedule([]))
try:
    best_schedule([(2, 2, 10)])
except ValueError:
    print("empty duration rejected")

Output

schedule: (10, [0, 3])
empty: (0, [])
empty duration rejected

Costs and limits

Sorting and n binary searches cost O(n log n), with O(n) DP and reconstruction storage. The n<=16 fixture also permits an independent exhaustive-subset oracle in tests. Real schedules may need resources, dependencies, setup costs or fairness constraints that this one-resource interval model does not express.

Common Mistakes

• Use the declared half-open boundary when testing compatibility.
• An optimal total alone does not verify that the reconstructed jobs are compatible.

Connected lessons

Python bisect: binary position search does not make list insertion logarithmic, Python 0/1 knapsack: descending capacity prevents item reuse, Python expiry exercise: separate pending, active and expired records at exact boundaries.

Check this related boundary

Python exercise: validate half-open reservations before accepting a batch.