Chapter 6.1: Weighted Interval Scheduling: A Recursive Procedure

The Weighted INterval Scheduling Problem is a problem in which each interval has a certain value (or weight), and we want to accept a set of maximum value.

Two intervals are compatible if they do not overlap. The goal of our current problem is to select a subset S {1, … , n} of mutually compatible intervals so as to maximize the sum of the values of the selected intervals.

These