براهين الاستبدال الجشعة والأمثلة المضادة

def schedule(intervals):
    if any(start >= finish for start, finish in intervals):
        raise ValueError("Intervals must have positive duration")
    selected = []
    last_finish = None
    for start, finish in sorted(intervals, key=lambda item: (item[1], item[0])):
        if last_finish is None or start >= last_finish:
            selected.append((start, finish))
            last_finish = finish
    return selected

print(schedule([(0, 3), (1, 2), (2, 4), (3, 5), (4, 6)]))
print(schedule([]))

[(1, 2), (2, 4), (4, 6)]
[]

تتوافق المجالات التي تتلامس نهاياتها. وينتج الفرز والاختيار حلا أمثل واحدا، وليس جميع الجداول المثلى.

from itertools import combinations

def best_reward(intervals):
    optimum = 0
    for count in range(len(intervals) + 1):
        for subset in combinations(intervals, count):
            ordered = sorted(subset, key=lambda item: item[0])
            if all(ordered[i - 1][1] <= ordered[i][0] for i in range(1, count)):
                optimum = max(optimum, sum(item[2] for item in subset))
    return optimum

intervals = [(0, 2, 4), (2, 4, 4), (0, 4, 10)]
print(best_reward(intervals))
print(sum(item[2] for item in intervals[:2]))

10
8

يخسر جدول صحيح من مجالين أمام مجال واحد أعلى عائدا، فيثبت أن أمثلية العدد لا تعني أمثلية العائد.