File WeightedIntervals.h

↰ Parent directory (ADS/optimization)

The independent set of weighted intervals of section 13.2: among n intervals [ a_i , b_i ), open on the right, of weights w_i, a set of disjoint ones of largest weight.

Definition (`ADS/optimization/WeightedIntervals.h`)

Program Listing for File WeightedIntervals.h

Detailed Description

With the intervals by increasing right end and pred[ i ] the largest j < i with b_{j-1} <= a_{i-1} (0 if none), :math:`[: DP[ i ] = max{ DP[ i - 1 ] , w_{i-1} + DP[ pred[ i ] ] } ,

` DP[ 0 ] = 0, and the set is read back from DP[ n ]; the predecessors come from one scan of the 2 n ends sorted, so that maxinterval() takes O( n log n ) time for the sort and O( n ) for the rest.

The contracts [see File Contract.h]: each interval has a < b and a weight not negative; the intervals chosen are disjoint and weigh the value found (checked at level 3). The operations are defined in WeightedIntervals.tpp.