Greedy

1def max_non_overlapping(intervals):2    """3    Select the most intervals that do not overlap.4 5    Sort by END time, not start. Exchange argument: the interval that ends6    soonest leaves the most room for everything after it, so some optimal7    solution contains it.8    """9    intervals.sort(key=lambda pair: pair[1])10 11    count = 012    last_end = float("-inf")13    for start, end in intervals:14        if start >= last_end:15            count += 116            last_end = end17    return count18 19 20def min_removals_to_fit(items, capacity):21    """Sort so the cheapest concession comes first, then take while it fits."""22    items.sort()23    used = 024    taken = 025    for item in items:26        if used + item > capacity:27            break28        used += item29        taken += 130    return taken