Weighted Interval Scheduling

Sort by finish time; dp[i] best profit among intervals ending by time order—binary search predecessor for O(n log n).

Why this shows up in the real world

Room booking max revenue. CPU interval scheduling with weights.

Core idea (explained for students)

After sorting, dp[i]=max(dp[i-1], w_i + dp[p(i)]) where p(i) is last non-overlapping index.

Try this in Python

def weighted_interval(intervals: list[tuple[int, int, int]]) -> int:
    intervals = sorted(intervals, key=lambda x: x[1])
    ends = [e for _, e, _ in intervals]
    import bisect

    dp = [0]
    best = 0
    for s, e, w in intervals:
        j = bisect.bisect_right(ends, s) - 1
        take = w + (dp[j + 1] if j >= 0 else 0)
        best = max(best, take)
        dp.append(best)
    return best


print(weighted_interval([(1, 3, 5), (2, 5, 6), (4, 6, 5), (6, 7, 4)]))

Common mistakes

• Unsorted intervals—wrong predecessor.
• Tie-breaking equal finish times.

Key takeaways

• Coordinate compress times if huge integers sparse.